Maximum Subarray

What the problem is really asking

We need the contiguous part of the array whose sum is as large as possible.

So at every index, we have to decide:

"Should I continue the current subarray, or should I start fresh from here?"

Intuition

If the running sum becomes harmful, carrying it forward only makes future sums worse.

That means the best subarray ending at position i must be one of only two things:

• just nums[i]
• or the previous best ending sum plus nums[i]

Brute-force idea

The slow method is:

• choose every possible starting index
• extend to every possible ending index
• compute all sums

That takes O(n^2) or worse depending on how the sums are computed.

Optimized approach

Use Kadane's algorithm.

Keep:

• current: best subarray sum ending at the current index
• best: best subarray sum seen anywhere so far

For each new number:

• either start a new subarray from this number
• or extend the old subarray

Take whichever is larger.

class Solution {
    public int maxSubArray(int[] nums) {
        int current = nums[0];
        int best = nums[0];

        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);
            best = Math.max(best, current);
        }

        return best;
    }
}

Dry run

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

• start: current = -2, best = -2
• see 1: better to restart, so current = 1, best = 1
• see -3: current = -2, best = 1
• see 4: restart, so current = 4, best = 4
• see -1: extend, so current = 3
• see 2: extend, so current = 5, best = 5
• see 1: extend, so current = 6, best = 6

The maximum subarray sum is 6.

Common mistakes

1. Thinking you need to remember the whole subarray

To compute the best sum, you only need the running best ending here.

2. Resetting only when the sum becomes exactly zero

The real question is not about zero. It is whether carrying the old sum is worse than starting fresh.

3. Forgetting negative-only arrays

The answer can still be negative, so initialize from nums[0], not from 0.

Complexity

Time Complexity: O(n)

Space Complexity: O(1)