Free lesson · DSA Mastery - Interview Prep, End to End

Maximum Subarray

Medium8 min readdsakadane-s-algorithm

Maximum Subarray

Maximum Subarray is the problem Kadane's algorithm was invented for, and one of the most-asked questions in technical interviews. Given an integer array, find the contiguous subarray with the largest sum and return that sum. We climb four approaches: brute force over all subarrays (O(n³)), an optimized brute force with a running inner sum (O(n²)), divide and conquer (O(n log n)), and the optimal Kadane single-pass running-state scan (O(n), O(1)).

The arc here is the whole point: each approach exposes a little more structure, and Kadane is the payoff - the realization that the best subarray ending at each position can be carried forward in a single variable.

The Problem

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

Example 1:

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

Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.

Example 2:

Input:  nums = [1]
Output: 1

Example 3:

Input:  nums = [5, 4, -1, 7, 8]
Output: 23

Explanation: The entire array sums to 23.

Constraints:

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

Approaches Overview

The subarray must be non-empty, so the answer can be negative (when all elements are negative, it's the single largest element).

Approach 1: Brute Force (All Subarrays)

The Idea

Enumerate every subarray (i, j) and sum it from scratch, tracking the maximum. Three nested loops: two for the bounds, one for the sum.

Logic Flowchart

graph TD
    A["best = -infinity"] --> B["For start i = 0 to n-1"]
    B --> C["For end j = i to n-1"]
    C --> D["sum = 0; for t = i..j: sum += nums[t]"]
    D --> E["best = max(best, sum)"]
    E --> F{"More j?"}
    F -->|Yes| C
    F -->|No| G{"More i?"}
    G -->|Yes| B
    G -->|No| H["Return best"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the cubic brute force. For every pair of start and end indices, we sum the subarray from scratch and track the maximum. Re-summing each subarray with an inner loop gives cubic time.

Code

public static int maxSubArrayBrute(int[] nums) {
    int best = Integer.MIN_VALUE, n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int sum = 0;
            for (int t = i; t <= j; t++) sum += nums[t];
            best = Math.max(best, sum);
        }
    }
    return best;
}

This Java code sums every subarray from scratch using three nested loops and tracks the maximum. The repeated inner summation gives cubic time.

Complexity

Time: O(n³). Space: O(1).

Re-summing each subarray is the obvious waste - the inner loop recomputes overlapping sums.

Approach 2: Brute Force (Running Inner Sum)

The Idea

Fix the start i, then extend j while maintaining a running sum - no need to re-sum. This drops one loop: O(n²).

Logic Flowchart

graph TD
    A["best = -infinity"] --> B["For start i = 0 to n-1"]
    B --> C["sum = 0"]
    C --> D["For end j = i to n-1"]
    D --> E["sum += nums[j]"]
    E --> F["best = max(best, sum)"]
    F --> G{"More j?"}
    G -->|Yes| D
    G -->|No| H{"More i?"}
    H -->|Yes| B
    H -->|No| I["Return best"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the quadratic brute force. For each start, we extend the end while maintaining a running sum and tracking the maximum. Dropping the re-summation removes one loop, giving quadratic time.

Code

public static int maxSubArrayQuadratic(int[] nums) {
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            best = Math.max(best, sum);
        }
    }
    return best;
}

This Java code fixes each start and extends the end with a running sum, tracking the maximum. Two nested loops give quadratic time.

Complexity

Time: O(n²). Space: O(1).

Still too slow at 10^5. The leap to linear comes from not restarting the start pointer at all.

Approach 3: Divide and Conquer

The Idea

Split the array in half. The maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint. Recurse on the halves; for the crossing case, compute the best suffix of the left half plus the best prefix of the right half. Combine. T(n) = 2T(n/2) + O(n) → O(n log n).

Logic Flowchart

graph TD
    A["solve(lo, hi)"] --> B{"lo == hi?"}
    B -->|Yes| C["return nums[lo]"]
    B -->|No| D["mid = (lo+hi)/2"]
    D --> E["leftBest = solve(lo, mid)"]
    E --> F["rightBest = solve(mid+1, hi)"]
    F --> G["crossBest = maxSuffix(lo,mid) + maxPrefix(mid+1,hi)"]
    G --> H["return max(leftBest, rightBest, crossBest)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows divide and conquer. We split at the midpoint and recurse on each half. The crossing case combines the best suffix of the left half with the best prefix of the right half. The answer is the maximum of the left, right, and crossing results.

Code

public static int maxSubArrayDivide(int[] nums) {
    return solve(nums, 0, nums.length - 1);
}

private static int solve(int[] nums, int lo, int hi) {
    if (lo == hi) return nums[lo];
    int mid = (lo + hi) >>> 1;
    int leftBest = solve(nums, lo, mid);
    int rightBest = solve(nums, mid + 1, hi);

    int suffix = Integer.MIN_VALUE, s = 0;
    for (int i = mid; i >= lo; i--) { s += nums[i]; suffix = Math.max(suffix, s); }
    int prefix = Integer.MIN_VALUE; s = 0;
    for (int i = mid + 1; i <= hi; i++) { s += nums[i]; prefix = Math.max(prefix, s); }

    return Math.max(Math.max(leftBest, rightBest), suffix + prefix);
}

This Java code recurses on each half and computes a crossing candidate by scanning outward from the midpoint for the best suffix on the left and best prefix on the right. It returns the maximum of the left, right, and crossing sums.

Complexity

Time: O(n log n). Space: O(log n) recursion.

Elegant, and a common interview follow-up - but Kadane beats it.

Approach 4: Kadane - Optimal

The Idea

Carry one running value: current = the maximum sum of a subarray ending at the current index. At each element, either extend the previous run or start fresh: current = max(nums[i], current + nums[i]). Track the global best. One pass, O(1) space.

Logic Flowchart

graph TD
    A["current = nums[0]<br/>best = nums[0]"] --> B["For i = 1 to n-1"]
    B --> C["current = max(nums[i], current + nums[i])"]
    C --> D["best = max(best, current)"]
    D --> E{"More?"}
    E -->|Yes| B
    E -->|No| F["Return best"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Kadane's algorithm. We carry the best sum of a subarray ending at the current index. At each element we either extend the previous run or start fresh, then update the global best. A single pass with constant space.

Code

public static int maxSubArray(int[] nums) {
    int current = nums[0], 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;
}

// Usage:
// maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}) -> 6
// maxSubArray(new int[]{5,4,-1,7,8})            -> 23

This Java code initializes the running and global best to the first element, then for each subsequent element extends the previous run or starts fresh, updating the global best. One pass, constant space.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Each frame shows the element, the extend-or-restart decision, current, and best:

graph LR
    F0["i=0 -2<br/>current=-2 best=-2"]
    F1["i=1 1: max(1,-2+1=-1)=1<br/>restart, current=1 best=1"]
    F2["i=3 4: max(4,-2+4=2)=4<br/>restart, current=4 best=4"]
    F3["i=4..6 -1,2,1<br/>extend: 3,5,6<br/>current=6 best=6"]
    F4["i=7 -5: 6-5=1<br/>extend, best stays 6"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#b45309,stroke:#f59e0b,color:#f1f5f9

This walkthrough traces minus two, one, minus three, four, minus one, two, one, minus five, four. The run restarts at one, then restarts at four, then extends through minus one, two, one to reach six - the subarray four, minus one, two, one. Later elements don't beat six. The answer is six.

Result: 6 (the subarray [4, -1, 2, 1]).

Complexity

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

Complexity Comparison

The whole algorithm is one line: current = max(nums[i], current + nums[i]). Everything else - recovering indices, handling all-negatives, variants - builds on that recurrence.

Variations & Follow-ups

How do you recover the actual subarray, not just the sum?

Track where the current run started: when you "start fresh," set start = i; when current produces a new best, record [start, i] as the best window.

What if the array is all negative?

The non-empty constraint means the answer is the largest single element. Kadane handles this naturally by initializing best = nums[0] and using max(nums[i], ...) - it never forces an empty subarray.

What if an empty subarray were allowed (sum 0)?

Then clamp the answer with max(0, best) - but read the problem carefully; the classic version forbids empty.

Why is divide and conquer worth knowing if Kadane wins?

It's a frequent interview follow-up ("can you solve it without Kadane?") and the crossing-subarray idea generalizes to segment-tree range-max-subarray queries.

What about overflow?

Max subarray sum is at most 10^5 * 10^4 = 10^9, within int, but long is safe if constraints grow.

What about edge cases?

• Single element: Returns that element (Example 2).
• All positive: Returns the total (Example 3).
• All negative: Returns the largest element.
• Mix: Returns the best contiguous run.

Common Interview Pitfalls

• Initializing best = 0. Breaks the all-negative case; initialize to nums[0].
• Allowing an empty subarray when forbidden. Don't reset current to 0; reset to nums[i].
• Re-summing subarrays. The quadratic/cubic trap; carry the running value.
• Forgetting to update best every step. The best run may end mid-array, not at the last element.

Why This Problem Matters

Maximum Subarray is Kadane's algorithm, and Kadane is the foundation for every problem in this module. The recurrence current = max(nums[i], current + nums[i]) - "extend or restart" - is one of the most reusable single-line algorithms in all of interviewing, and the running-state mindset it teaches powers products, circular arrays, deletions, and turbulence alike.

The next topic, Best Sightseeing Pair, looks nothing like a max-subarray problem at first glance - but it dissolves into Kadane the moment you reframe it as "carry the best left-side contribution forward as you scan right."

Back to DSA Mastery - Interview Prep, End to End