Maximum Subarray Sum — Kadane's Algorithm

The insight

At each element, either extend current subarray or start fresh. Whichever is larger.

Kadane's algorithm

int maxSum = nums[0], curSum = nums[0];
for (int i = 1; i < n; i++) {
  curSum = Math.max(nums[i], curSum + nums[i]);
  maxSum = Math.max(maxSum, curSum);
}
return maxSum;

All negative case

Return the largest (least negative) element. Kadane handles it naturally since we compare nums[i] alone vs curSum + nums[i].

Return the subarray

Track start + end indices. When we 'start fresh', update start = i. When maxSum updates, record end.