Topics › Arrays › Medium

Print subarray with maximum subarray sum (extended version of above problem)

Medium TUF ID 2761 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an integer array nums. Instead of only the maximum subarray sum (the previous problem, Kadane’s algorithm), return the subarray itself: the contiguous block of elements whose sum is as large as possible.

Several subarrays can share the maximum sum, for example in [1, -1, 2] both [1, -1, 2] and [2] sum to 2. To make the answer unique, this article uses the rule: among all subarrays with the maximum sum, return the one that starts earliest; if several start at the same index, return the shortest. This is exactly what the natural extension of Kadane’s algorithm produces, and the brute-force methods are written to follow the same rule so that all approaches agree. For an empty input return an empty array.

Constraints: 0 ≤ n ≤ 10^5, -10^9 ≤ nums[i] ≤ 10^9. Sums may exceed int, so accumulate in long.

Example 1

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
answer = [4, -1, 2, 1]        // sum 6

Example 2

nums = [1, -1, 2]
answer = [1, -1, 2]           // sum 2; [2] also has sum 2 but starts later

Example 3

nums = [-3, -1, -2]
answer = [-1]                 // all negative, so the best subarray is the single largest element

Approach 1: Brute force

Intuition. Enumerate every subarray by its start i and end j, compute its sum from scratch, and remember the (i, j) of the best one. Because the loops go through starts in increasing order and, for each start, ends in increasing order, updating only on a strictly larger sum automatically implements the tie-breaking rule: the first (i, j) reaching the maximum has the smallest i, and among those the smallest j.

Algorithm.

1. Set best = -∞, bestStart = 0, bestEnd = -1 (an empty range).
2. For every i, for every j ≥ i: compute sum(nums[i..j]) with a third loop.
3. If sum > best, record best = sum, bestStart = i, bestEnd = j.
4. Return a copy of nums[bestStart..bestEnd].

static int[] bruteForce(int[] nums) {
    int n = nums.length;
    long best = Long.MIN_VALUE;
    int bestStart = 0, bestEnd = -1;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long sum = 0;
            for (int k = i; k <= j; k++) sum += nums[k];
            if (sum > best) {
                best = sum;
                bestStart = i;
                bestEnd = j;
            }
        }
    }
    return Arrays.copyOfRange(nums, bestStart, bestEnd + 1);
}

Complexity. Time O(n^3). Space O(1) beyond the returned copy.

Arrays.copyOfRange(nums, from, to) copies indices from (inclusive) to to (exclusive); with bestStart = 0 and bestEnd = -1 it returns an empty array, which is the right answer for empty input.

Approach 2: Better, running sum per start

Intuition. As in Kadane’s problem, the inner recomputation is wasteful: for a fixed start, moving the end one step right adds a single element. Keep a running sum and the method drops to quadratic time while keeping the same tie-breaking behaviour.

Algorithm.

1. Same bookkeeping as before.
2. For every i: sum = 0; for every j ≥ i: sum += nums[j]; update the record if sum > best.
3. Return the copy.

static int[] better(int[] nums) {
    int n = nums.length;
    long best = Long.MIN_VALUE;
    int bestStart = 0, bestEnd = -1;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum > best) {
                best = sum;
                bestStart = i;
                bestEnd = j;
            }
        }
    }
    return Arrays.copyOfRange(nums, bestStart, bestEnd + 1);
}

Complexity. Time O(n^2). Space O(1) beyond the output.

Approach 3: Optimal, Kadane’s algorithm with bookkeeping

Intuition. Kadane’s algorithm carries current, the sum of the subarray it is currently building, and resets it to 0 when it goes negative. The subarray being built always begins right after the last reset, so one extra variable, start, records that position: it is 0 initially and becomes i + 1 whenever we reset at index i. Whenever current beats the best sum seen so far, the best subarray is nums[start..i], so we record bestStart = start and bestEnd = i.

Two details make the tie-breaking match the brute force:

• We update only when current is strictly greater than best. The first time the maximum sum is reached fixes the end index, which is the smallest possible end for that sum.
• We reset only when current is strictly negative. A carried sum of exactly 0 is kept, so a subarray like [1, -1, 2] is reported in full rather than as [2]. Both have the same sum, but keeping the zero-sum prefix gives the earliest start.

Why is the recorded start the earliest possible for a maximum-sum subarray? Let the maximum be M, reached first at end index e with recorded start s. Kadane’s start is the earliest index whose prefix sum is minimal among all prefixes up to e (every reset happens exactly when the running prefix drops strictly below the previous minimum). If some other maximum-sum subarray [s', e'] had s' < s, then the prefix at s' would be strictly larger than the prefix at s, and the subarray [s, e'] would have a sum strictly larger than M, a contradiction.

Algorithm.

1. Set best = -∞, current = 0, start = 0, bestStart = 0, bestEnd = -1.
2. For every index i: current += nums[i].
   • If current > best: best = current, bestStart = start, bestEnd = i.
   • If current < 0: current = 0, start = i + 1.
3. Return a copy of nums[bestStart..bestEnd].

static int[] optimal(int[] nums) {
    long best = Long.MIN_VALUE, current = 0;
    int start = 0, bestStart = 0, bestEnd = -1;
    for (int i = 0; i < nums.length; i++) {
        current += nums[i];
        if (current > best) {
            best = current;
            bestStart = start;
            bestEnd = i;
        }
        if (current < 0) {
            current = 0;
            start = i + 1;
        }
    }
    return Arrays.copyOfRange(nums, bestStart, bestEnd + 1);
}

Dry run on nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Result: nums[3..6] = [4, -1, 2, 1].

Complexity. Time O(n): one pass. Space O(1) extra; the output copy is O(length of answer).

Edge cases and pitfalls

• Empty array. bestEnd stays -1 and copyOfRange(nums, 0, 0) returns an empty array in all three methods.
• All negative. The strict < reset still records each element as a candidate before clearing, so [-3, -1, -2] returns [-1]. Resetting before recording would return an empty range or a wrong one.
• Ties. [1, -1, 2] returns [1, -1, 2], and [2, -2, 3, -3, 3] returns [2, -2, 3]. If your platform expects a different tie-breaking (for example the shortest subarray), change the reset to current <= 0 and start handling accordingly; make sure the brute force you test against uses the same rule.
• Forgetting to move start. Setting start = i + 1 at the reset, not at the next iteration, is what keeps start and current in sync.
• Recording start lazily. Some implementations set start = i when current == 0 at the top of the loop instead; that variant resets on zero as well, which changes which of several equal-sum subarrays is reported. Pick one convention and apply it everywhere.
• Overflow. [Integer.MAX_VALUE, Integer.MAX_VALUE, -1] must return the first two elements; with int sums the total would wrap to a negative number and the answer would be a single element.
• Returning indices instead. If the problem wants (start, end) rather than the elements, return {bestStart, bestEnd}; the bookkeeping is identical.

Related problems

• Kadane’s Algorithm is the sum-only version this problem extends.
• Maximum Product Subarray in an Array changes the operation to multiplication and needs both a running max and a running min.
• Stock Buy and Sell can be solved with Kadane on consecutive differences; reporting the buy and sell days is the same bookkeeping.
• Longest subarray with sum K also reasons about prefix sums and their earliest occurrence.