Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum Sum Subarray with Indices

MEDIUMProblemSolveExternal Links

Description

Given an array of integers arr[], find the contiguous subarray containing only non-negative numbers that has the maximum sum. Return the subarray itself (not just the sum).

Tie-breaking rules:

  1. If multiple subarrays have the same maximum sum, return the one with the longest length.
  2. If there is still a tie, return the subarray with the smallest starting index.

Special case: If the array contains only negative numbers, return [-1].

A subarray is a contiguous non-empty sequence of elements within an array. The key constraint here is that the subarray must contain only non-negative numbers — any negative number breaks the subarray.

This problem combines the ideas of subarray identification with careful boundary handling and tie-breaking logic.

Examples

Example 1

Input: arr = [1, 2, 3]

Output: [1, 2, 3]

Explanation: Every element is non-negative, so the entire array is one valid subarray. Its sum is 1+2+3 = 6, and since it's the only candidate, the answer is [1, 2, 3].

Example 2

Input: arr = [-1, 2]

Output: [2]

Explanation: The non-negative subarrays are: [2] (sum=2). The element -1 is negative, so it cannot be part of any valid subarray. The only valid subarray is [2].

Example 3

Input: arr = [1, 2, 5, -7, 2, 6]

Output: [1, 2, 5]

Explanation: The non-negative segments are:

  • [1, 2, 5] → sum = 8, length = 3
  • [2, 6] → sum = 8, length = 2

Both have the same sum (8), but [1, 2, 5] is longer (length 3 > 2) and also starts earlier (index 0 < index 4). So the answer is [1, 2, 5].

Example 4

Input: arr = [-3, -5, -1]

Output: [-1]

Explanation: All elements are negative. No valid non-negative subarray exists. Per the problem rules, we return [-1] to indicate this.

Constraints

  • 1 ≤ arr.size() ≤ 10^6
  • -10^5 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

The simplest approach is to enumerate every possible subarray, filter out those containing any negative element, compute their sums, and track the one with the maximum sum (with tie-breaking on length and starting index).

For each pair of indices (i, j) where i ≤ j, we check if all elements in arr[i..j] are non-negative. If they are, we compute the sum and compare it against our current best.

This is straightforward but wasteful — we're checking many subarrays that overlap with negative elements, and we're recomputing sums from scratch for each subarray.

Step-by-Step Explanation

Let's trace with arr = [1, 2, 5, -7, 2, 6], looking for the max-sum non-negative subarray:

Step 1 (i=0, j=0): Subarray [1]. All non-negative? Yes. Sum = 1. Best: sum=1, subarray=[1].

Step 2 (i=0, j=1): Subarray [1, 2]. All non-negative? Yes. Sum = 3. Best: sum=3, subarray=[1,2].

Step 3 (i=0, j=2): Subarray [1, 2, 5]. All non-negative? Yes. Sum = 8. Best: sum=8, subarray=[1,2,5].

Step 4 (i=0, j=3): Subarray [1, 2, 5, -7]. Contains -7 (negative). Skip.

Steps 5-6: All subarrays starting at i=0 with j ≥ 3 contain -7. Skip.

Steps 7-9: Subarrays starting at i=1: [2] sum=2, [2,5] sum=7, [2,5,-7] has negative. All worse than sum=8.

Step 10: i=2: [5] sum=5, [5,-7] negative. Worse.
Step 11: i=3: [-7] negative. Skip.
Step 12: i=4: [2] sum=2, [2,6] sum=8. Same sum=8 as best! But length=2 < 3. Best stays [1,2,5].
Step 13: i=5: [6] sum=6. Worse.

Result: [1, 2, 5] with sum=8.

Brute Force — Check All Non-Negative Subarrays — Watch how the brute force enumerates subarrays, skipping any that contain negative elements, and tracking the maximum sum with tie-breaking.

Algorithm

  1. Initialize bestSum = 0, bestStart = -1, bestEnd = -1
  2. For each starting index i from 0 to n-1:
    • If arr[i] < 0, skip (can't start a non-negative subarray with negative)
    • Initialize sum = 0
    • For each ending index j from i to n-1:
      • If arr[j] < 0, break (subarray can't extend past a negative)
      • sum += arr[j]
      • Compare sum against bestSum with tie-breaking
  3. If bestStart == -1 (all negative), return [-1]
  4. Return arr[bestStart..bestEnd]

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> maxSumSubarray(vector<int>& arr) {
        int n = arr.size();
        long long bestSum = -1;
        int bestStart = -1, bestEnd = -1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] < 0) continue;
            long long sum = 0;
            for (int j = i; j < n; j++) {
                if (arr[j] < 0) break;
                sum += arr[j];
                int len = j - i + 1;
                int bestLen = bestEnd - bestStart + 1;
                if (sum > bestSum || 
                    (sum == bestSum && len > bestLen) ||
                    (sum == bestSum && len == bestLen && i < bestStart)) {
                    bestSum = sum;
                    bestStart = i;
                    bestEnd = j;
                }
            }
        }
        
        if (bestStart == -1) return {-1};
        return vector<int>(arr.begin() + bestStart, arr.begin() + bestEnd + 1);
    }
};
class Solution:
    def maxSumSubarray(self, arr):
        n = len(arr)
        best_sum = -1
        best_start = -1
        best_end = -1
        
        for i in range(n):
            if arr[i] < 0:
                continue
            current_sum = 0
            for j in range(i, n):
                if arr[j] < 0:
                    break
                current_sum += arr[j]
                length = j - i + 1
                best_len = best_end - best_start + 1 if best_start >= 0 else 0
                if (current_sum > best_sum or
                    (current_sum == best_sum and length > best_len) or
                    (current_sum == best_sum and length == best_len and i < best_start)):
                    best_sum = current_sum
                    best_start = i
                    best_end = j
        
        if best_start == -1:
            return [-1]
        return arr[best_start:best_end + 1]
import java.util.*;

class Solution {
    List<Integer> maxSumSubarray(int[] arr) {
        int n = arr.length;
        long bestSum = -1;
        int bestStart = -1, bestEnd = -1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] < 0) continue;
            long sum = 0;
            for (int j = i; j < n; j++) {
                if (arr[j] < 0) break;
                sum += arr[j];
                int len = j - i + 1;
                int bestLen = bestStart >= 0 ? bestEnd - bestStart + 1 : 0;
                if (sum > bestSum ||
                    (sum == bestSum && len > bestLen) ||
                    (sum == bestSum && len == bestLen && i < bestStart)) {
                    bestSum = sum;
                    bestStart = i;
                    bestEnd = j;
                }
            }
        }
        
        if (bestStart == -1) return Arrays.asList(-1);
        List<Integer> result = new ArrayList<>();
        for (int i = bestStart; i <= bestEnd; i++) result.add(arr[i]);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case (all non-negative elements), we check all n(n+1)/2 subarrays. Each subarray takes O(1) to extend (running sum), so total is O(n²).

Space Complexity: O(1)

We only use a few variables to track the best subarray. The output array doesn't count toward auxiliary space.

Why This Approach Is Not Efficient

With n up to 10^6, an O(n²) algorithm performs up to 5 × 10^11 operations — impossibly slow.

The key inefficiency: we're re-examining the same non-negative segments multiple times. For example, if arr = [1, 2, 5], we check [1], [1,2], [1,2,5] starting from i=0, then [2], [2,5] starting from i=1, then [5] starting from i=2. But these all belong to the same contiguous non-negative segment [1, 2, 5]. The sum of the entire segment is always the maximum within it (since all elements are non-negative, adding more elements never decreases the sum).

Critical insight: Since we only care about non-negative elements, every element in a valid subarray contributes positively (or zero) to the sum. Therefore, the maximum-sum non-negative subarray within any contiguous non-negative segment is always the entire segment itself. We just need to identify each segment and compute its sum — which can be done in a single pass.

Optimal Approach - Single Pass Segment Scan

Intuition

Since we need subarrays containing only non-negative numbers, the array naturally breaks into segments separated by negative numbers.

For example, arr = [1, 2, 5, -7, 2, 6] has two non-negative segments:

  • Segment 1: [1, 2, 5] (indices 0-2)
  • Segment 2: [2, 6] (indices 4-5)

Within each segment, since all values are ≥ 0, adding more elements never hurts the sum. The maximum sum subarray within a non-negative segment is always the entire segment.

So the algorithm is simple:

  1. Scan left to right, accumulating a running sum of non-negative elements
  2. When we hit a negative number, we've found the end of a segment — compare it against our best
  3. Reset and start a new segment
  4. After the loop, check the last segment

The tie-breaking (longest length, then earliest start) is handled naturally: we update the best only when the new segment is strictly better in sum, or has the same sum but is longer, or has the same sum and length but starts earlier (which can't happen since we scan left to right).

Step-by-Step Explanation

Let's trace with arr = [1, 2, 5, -7, 2, 6]:

Initialize: currentSum = 0, segStart = 0, bestSum = -1, bestStart = -1, bestEnd = -1.

Step 1 (index 0): arr[0] = 1 ≥ 0. currentSum = 0 + 1 = 1. Continue.

Step 2 (index 1): arr[1] = 2 ≥ 0. currentSum = 1 + 2 = 3. Continue.

Step 3 (index 2): arr[2] = 5 ≥ 0. currentSum = 3 + 5 = 8. Continue.

Step 4 (index 3): arr[3] = -7 < 0. Segment [1, 2, 5] ends!

  • segSum = 8, segLen = 3 (indices 0-2)
  • Compare: 8 > bestSum(-1). Update! bestSum = 8, bestStart = 0, bestEnd = 2.
  • Reset: currentSum = 0, segStart = 4.

Step 5 (index 4): arr[4] = 2 ≥ 0. currentSum = 0 + 2 = 2. Continue.

Step 6 (index 5): arr[5] = 6 ≥ 0. currentSum = 2 + 6 = 8. End of array.

Step 7 (post-loop): Check last segment [2, 6].

  • segSum = 8, segLen = 2 (indices 4-5)
  • Compare: 8 == bestSum(8). Tie! Check length: 2 < 3. Best stays [1, 2, 5].

Result: [1, 2, 5].

Single Pass Segment Scan — Identify Non-Negative Segments — Watch how we scan left to right, accumulating non-negative elements into segments. When a negative number appears, we finalize the current segment and compare it against our best.

Algorithm

  1. Initialize currentSum = 0, segStart = 0, bestSum = -1, bestStart = -1, bestEnd = -1
  2. For each index i from 0 to n-1:
    a. If arr[i] >= 0:
    • Add arr[i] to currentSum
    • Compare current segment against best (using tie-breaking rules)
    • If better, update bestSum, bestStart, bestEnd
      b. If arr[i] < 0:
    • Reset: currentSum = 0, segStart = i + 1
  3. If bestStart == -1, return [-1] (all negative)
  4. Return arr[bestStart..bestEnd]

Tie-breaking comparison: New segment is better if:

  • segSum > bestSum, OR
  • segSum == bestSum AND segLen > bestLen, OR
  • segSum == bestSum AND segLen == bestLen AND segStart < bestStart

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> maxSumSubarray(vector<int>& arr) {
        int n = arr.size();
        long long currentSum = 0, bestSum = -1;
        int segStart = 0, bestStart = -1, bestEnd = -1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] >= 0) {
                currentSum += arr[i];
                int segLen = i - segStart + 1;
                int bestLen = bestStart >= 0 ? bestEnd - bestStart + 1 : 0;
                
                if (currentSum > bestSum ||
                    (currentSum == bestSum && segLen > bestLen) ||
                    (currentSum == bestSum && segLen == bestLen && segStart < bestStart)) {
                    bestSum = currentSum;
                    bestStart = segStart;
                    bestEnd = i;
                }
            } else {
                // Negative element — reset segment
                currentSum = 0;
                segStart = i + 1;
            }
        }
        
        if (bestStart == -1) return {-1};
        return vector<int>(arr.begin() + bestStart, arr.begin() + bestEnd + 1);
    }
};
class Solution:
    def maxSumSubarray(self, arr):
        n = len(arr)
        current_sum = 0
        best_sum = -1
        seg_start = 0
        best_start = -1
        best_end = -1
        
        for i in range(n):
            if arr[i] >= 0:
                current_sum += arr[i]
                seg_len = i - seg_start + 1
                best_len = best_end - best_start + 1 if best_start >= 0 else 0
                
                if (current_sum > best_sum or
                    (current_sum == best_sum and seg_len > best_len) or
                    (current_sum == best_sum and seg_len == best_len and seg_start < best_start)):
                    best_sum = current_sum
                    best_start = seg_start
                    best_end = i
            else:
                # Negative element — reset segment
                current_sum = 0
                seg_start = i + 1
        
        if best_start == -1:
            return [-1]
        return arr[best_start:best_end + 1]
import java.util.*;

class Solution {
    List<Integer> maxSumSubarray(int[] arr) {
        int n = arr.length;
        long currentSum = 0, bestSum = -1;
        int segStart = 0, bestStart = -1, bestEnd = -1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] >= 0) {
                currentSum += arr[i];
                int segLen = i - segStart + 1;
                int bestLen = bestStart >= 0 ? bestEnd - bestStart + 1 : 0;
                
                if (currentSum > bestSum ||
                    (currentSum == bestSum && segLen > bestLen) ||
                    (currentSum == bestSum && segLen == bestLen && segStart < bestStart)) {
                    bestSum = currentSum;
                    bestStart = segStart;
                    bestEnd = i;
                }
            } else {
                currentSum = 0;
                segStart = i + 1;
            }
        }
        
        if (bestStart == -1) return Arrays.asList(-1);
        List<Integer> result = new ArrayList<>();
        for (int i = bestStart; i <= bestEnd; i++) result.add(arr[i]);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once. Each element is processed in O(1) time — we either add it to the current sum or reset the segment. The comparisons and updates are all constant-time operations.

Space Complexity: O(1)

We use only a fixed number of variables (currentSum, segStart, bestSum, bestStart, bestEnd) regardless of input size. The output array is not counted as auxiliary space.

Why this works: The critical observation is that within a non-negative segment, every element contributes non-negatively to the sum. Therefore, the maximum-sum subarray within a segment is always the entire segment. We simply need to identify segments (split at negative numbers) and compare their sums — a single-pass operation.