Maximum Subarray (Kadane's)
Problem Description
Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6 (subarray [4,-1,2,1])
Example 2:
Input: nums = [5,4,-1,7,8]
Output: 23
DE Shaw Tier 2 — LC 53.
Kadane's algorithm O(n): curMax = max(num, curMax + num). globalMax = max(globalMax, curMax).
Talk-track: 'At each position, we decide: start fresh with just this element, or extend the previous subarray. curMax + num < num when curMax is negative — so we reset.'
Example Test Cases
Example 1
Input: [[-2,1,-3,4,-1,2,1,-5,4]]
Expected: 6
Example 2
Input: [[1]]
Expected: 1
Example 3
Input: [[5,4,-1,7,8]]
Expected: 23
Example 4
Input: [[-1,-2,-3]]
Expected: -1
Run your code to see the results