LeetCode 53 Maximum Subarray Sum - Problem Statement

Find the maximum sum of any contiguous subarray. This is the famous Maximum Subarray problem. You could use prefix sums: $\max(prefix[j] - prefix[i])$ for $j > i$. Track the minimum prefix seen so far.

But there's a simpler approach: Kadane's algorithm. At each position, either extend the current subarray or start fresh. $dp[i] = \max(nums[i], dp[i-1] + nums[i])$. The answer is $\max(dp[i])$. This runs in $O(n)$ time and $O(1)$ space.