Dynamic Programming
LC #53Medium
Maximum Subarray
Dynamic Programming
AmazonGoogleLinkedInMetaBloombergMicrosoftProblem
Find the contiguous subarray with the largest sum (Kadane's algorithm).
arraydynamic-programmingdivide-and-conquer
Constraints
- ›1 ≤ nums.length ≤ 10⁵
- ›-10⁴ ≤ nums[i] ≤ 10⁴
Example
Input
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]Output
6Why
Subarray [4,-1,2,1] has the largest sum = 6