There are O(n²) contiguous subarrays, but you do not need to look at them all. Kadane's algorithm notices that the best subarray ending at position i is either nums[i] alone or nums[i] glued onto the best subarray ending at i - 1.
Given a list of integers nums (at least one element), return the largest possible sum of a contiguous, non-empty subarray.
Examples
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: [4, -1, 2, 1] has sum 6.
Input: nums = [-3, -1, -2]
Output: -1
Explanation: The subarray must be non-empty, so the best is [-1].
Constraints
1 <= len(nums) <= 10**4- Elements may be negative; the answer may be negative.
- Aim for O(n) time and O(1) extra space.
Goals
- Track the best subarray sum that ends at the current index
- Decide at each element whether to extend the previous run or start fresh
- Solve an optimisation problem over all contiguous subarrays in one O(n) pass