122.Maximum Subarray

MediumBlind 75Greedy · 1/8

Problem

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

Examples

Input:  nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has sum 6.

Input:  nums = [1]
Output: 1

Input:  nums = [5,4,-1,7,8]
Output: 23
Explanation: The whole array is the best subarray.

Input:  nums = [-3,-1,-2]
Output: -1
Explanation: All values are negative, so the best is the single largest element.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

💡 Key Insight

Let cur be the best sum of a subarray that ends at index i. Either we extend the previous best (cur + nums[i]) or start fresh at nums[i] — and we should start fresh exactly when the running sum has become negative, because a negative prefix can only drag down anything after it. This is Kadane's algorithm: one pass, two variables.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Try every starting index i, extend the subarray one element at a time, and track the running sum. The best running sum seen anywhere is the answer.

Algorithm

best = nums[0].
For each i: sum = 0; for each j >= i: sum += nums[j], best = max(best, sum).
Return best.

Visualization

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

i=3: sums 4, 3, 5, 6, 1, 5   -> best becomes 6 at j=6 ([4,-1,2,1])

Code

java

class Solution {
    public int maxSubArray(int[] nums) {
        int best = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j]; // sum of nums[i..j]
                best = Math.max(best, sum);
            }
        }
        return best;
    }
}

Complexity

Time: O(n²) — every pair (i, j); too slow for n = 10^5.
Space: O(1).

Divide and Conquer

TimeO(n log n)SpaceO(log n)

Intuition

Split the array at mid. The best subarray lies entirely in the left half, entirely in the right half, or crosses the middle. The crossing case is the best suffix of the left half (ending at mid) plus the best prefix of the right half (starting at mid + 1), computable in linear time.

Algorithm

solve(lo, hi): if lo == hi, return nums[lo].
mid = (lo + hi) / 2; recursively get left and right.
Scan leftwards from mid for the max suffix sum, and rightwards from mid + 1 for the max prefix sum; cross = suffix + prefix.
Return max(left, right, cross).

Visualization

[-2, 1, -3, 4, -1 | 2, 1, -5, 4]
best suffix of left ending at -1: 4 + -1 = 3
best prefix of right starting at 2: 2 + 1 = 3
cross = 6  (beats left-only 4 and right-only 4)

Code

java

class Solution {
    public int maxSubArray(int[] nums) {
        return solve(nums, 0, nums.length - 1);
    }

    private int solve(int[] nums, int lo, int hi) {
        if (lo == hi) {
            return nums[lo];
        }
        int mid = lo + (hi - lo) / 2;
        int left = solve(nums, lo, mid);
        int right = solve(nums, mid + 1, hi);

        // best sum crossing the midpoint
        int sum = 0, bestSuffix = Integer.MIN_VALUE;
        for (int i = mid; i >= lo; i--) {
            sum += nums[i];
            bestSuffix = Math.max(bestSuffix, sum);
        }
        sum = 0;
        int bestPrefix = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= hi; i++) {
            sum += nums[i];
            bestPrefix = Math.max(bestPrefix, sum);
        }
        return Math.max(Math.max(left, right), bestSuffix + bestPrefix);
    }
}

Complexity

Time: O(n log n) — T(n) = 2T(n/2) + O(n).
Space: O(log n) — recursion depth.

Kadane's AlgorithmOptimal

TimeO(n)SpaceO(1)

Intuition

Walk left to right keeping cur, the best sum of a subarray ending at the current index. If cur has gone negative, it is better to throw it away and start over at nums[i]; otherwise extend it. The global answer is the maximum cur ever reaches. Starting best at nums[0] (not 0) handles all-negative arrays.

Algorithm

cur = nums[0], best = nums[0].
For i from 1: cur = max(nums[i], cur + nums[i]); best = max(best, cur).
Return best.

Dry Run

i    nums[i]   cur = max(nums[i], cur + nums[i])   best
0      -2        -2                                 -2
1       1        max(1, -1)  =  1   (restart)        1
2      -3        max(-3, -2) = -2                    1
3       4        max(4, 2)   =  4   (restart)        4
4      -1        3                                   4
5       2        5                                   5
6       1        6                                   6
7      -5        1                                   6
8       4        5                                   6

flowchart LR
    A["cur = -2"] -->|"cur < 0: restart at 1"| B["cur = 1"]
    B -->|"+(-3)"| C["cur = -2"]
    C -->|"cur < 0: restart at 4"| D["cur = 4"]
    D -->|"-1, +2, +1"| E["cur = 6<br/>best = 6"]
    E -->|"-5, +4"| F["cur = 5<br/>return best = 6"]

Code

java

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0];  // best sum of a subarray ending here
        int best = nums[0]; // best sum seen anywhere
        for (int i = 1; i < nums.length; i++) {
            // drop the running sum if it would only hurt
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

Complexity

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

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Divide and Conquer	O(n log n)	O(log n)
Kadane's Algorithm	O(n)	O(1)

Common Pitfalls

Initialising best = 0 — returns 0 for an all-negative array instead of the largest element.
Resetting cur to 0 before adding the current element and then comparing, which can also report 0 incorrectly for all-negative input.
Confusing subarray (contiguous) with subsequence — you cannot skip negative elements in the middle.
In divide and conquer, forgetting that the crossing sum must include both nums[mid] and nums[mid + 1].