50. Maximum Subarray

Try every contiguous subarray and track the maximum sum.

Approach

For each start i, accumulate sum as we extend the end j.

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (int j = i; j < n; j++) {
                s += nums[j];
                best = Math.max(best, s);
            }
        }
        return best;
    }
}

At index i, ask: is the best subarray ending here the one I was already extending, or should I start fresh? If my running sum has gone negative, it can only hurt future extensions — reset it.

Approach

1. cur = 0, best = -∞.
2. For each num:
   • cur = max(num, cur + num) (start fresh or extend).
   • best = max(best, cur).

Walk-through

nums = [-2,1,-3,4,-1,2,1,-5,4]

Answer: 6 from [4,-1,2,1].