Maximum Subarray (LC 53)

Pattern: Dynamic Programming / Kadane’s Algorithm
Difficulty: Medium
Key Concept: Either extend the best subarray ending at the previous index, or start fresh at the current element—whichever gives a larger sum.

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum.

A subarray is a consecutive portion of the array.

Input

• nums — integer array (non-empty)

Output

• int — maximum possible sum over all non-empty contiguous subarrays

Example

• nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (subarray [4, -1, 2, 1]).

---

1. Algorithm & Pseudocode

Brute force

1. Initialize best to nums[0] (or negative infinity if you prefer, but array is non-empty).
2. For each start index i from 0 to n - 1:
3. Set runSum = 0.
4. For each end index j from i to n - 1:
5. Add nums[j] to runSum.
6. If runSum > best, set best = runSum.
7. Return best.

Optimal (Kadane)

1. Initialize best = nums[0], cur = nums[0].
2. For each index k from 1 to n - 1:
3. Set cur = max(nums[k], cur + nums[k]) — either restart at nums[k] or extend the previous subarray.
4. Set best = max(best, cur).
5. Return best.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is correct
Every contiguous subarray is defined by a start i and end j with i ≤ j. The double loop visits all of them and tracks the maximum sum. Nothing is missed.

Why brute force is slow
There are (O(n^2)) subarrays, and the inner loop adds one element each time—still (O(n^2)) total work. For large (n), this is too slow.

Why Kadane works
Focus on subarrays that end at position k. The best one either:

• Starts fresh at k (only nums[k]), useful when everything before drags the sum down, or
• Extends the best subarray ending at k - 1, because that continuation adds nums[k] to a already-known optimal “tail.”

Taking the maximum of those two choices is exactly the best subarray ending at k. The global answer is the maximum of those “ending at k” values over all k.

Why we need “restart”
If cur becomes very negative, adding more positive numbers later might still lose to starting over at a large positive value. Example: [ -2, 1 ] — after -2, extending gives -1, but restarting at 1 gives 1.

ASCII — extending vs restarting

nums:  [-2,  1, -3,  4, ...]
              ^
           at k=1:  cur was -2
           max(1, -2+1) = max(1,-1) = 1  → fresh start wins

---

3. The Dry Run

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

Step	k	nums[k]	cur (after)	best (after)	Choice (conceptually)
init	0	-2	-2	-2	start
1	1	1	1	1	max(1, -2+1)=1
2	2	-3	-2	1	max(-3, 1-3)=-2
3	3	4	4	4	max(4, -2+4)=4
4	4	-1	3	4	max(-1, 4-1)=3
5	5	2	5	5	max(2, 3+2)=5
6	6	1	6	6	max(1, 5+1)=6
7	7	-5	1	6	max(-5, 6-5)=1
8	8	4	5	6	max(4, 1+4)=5

Result: 6.

---

4. Java Solution

Brute Force

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int best = nums[0];
        for (int i = 0; i < n; i++) {
            int runSum = 0;
            for (int j = i; j < n; j++) {
                runSum += nums[j];
                if (runSum > best) {
                    best = runSum;
                }
            }
        }
        return best;
    }
}

Time: (O(n^2)).
Space: (O(1)).

Optimal

class Solution {
    public int maxSubArray(int[] nums) {
        int best = nums[0];
        int cur = nums[0];
        for (int k = 1; k < nums.length; k++) {
            cur = Math.max(nums[k], cur + nums[k]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

Time: (O(n)) — single pass.
Space: (O(1)).

---

5. The “Java vs. Others” Edge

• Math.max avoids manual branches and reads clearly; Integer.MIN_VALUE is not needed if you initialize best and cur from nums[0] (array non-empty per problem).
• Kadane is often written with cur starting at 0 and different initialization; the version above matches the “ending at k” story and handles all-negative arrays (e.g. [-3,-2] → -2) because cur resets via max(nums[k], ...).
• No collections required—pure int accumulation is cache-friendly and simple on the JVM.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Tries every (i, j) subarray.
Optimal (Kadane)	(O(n))	(O(1))	One pass; constant extra variables.