( Kadane's Algorithm )
Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.
Example:
Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7
Note:
Your algorithm should run in O(n) time and use O(1) extra space.
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Solution #2 · O(n) Kadane
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check