Max Non-negative subarray sum

Problem

Find out the maximum sub-array of non negative numbers from an array. The sub-array should be continuous. That is, a sub-array created by choosing the second and fourth element and skipping the third element is invalid.

Maximum sub-array is defined in terms of the sum of the elements in the sub-array. Sub-array A is greater than sub-array B if sum(A) > sum(B).

Examples

Example 1

Input: [1, 2, 5, -7, 2, 3]
Output: [1, 2, 5]
Explanation: The two sub-arrays are [1, 2, 5] and [2, 3]. The answer is [1, 2, 5] as its sum is larger than [2, 3].

Notes

• If there is a tie, then compare with segment's length and return segment which has maximum length.
• If there is still a tie, then return the segment with minimum starting index.

Solution

Method 1 – Brute Force

Intuition

Try every possible subarray and check if it is non-negative. Track the one with the largest sum, breaking ties by length and then by starting index.

Approach

1. For every possible subarray, check if all elements are non-negative.
2. If so, compute its sum and compare to the best found so far (using sum, then length, then starting index as tiebreakers).
3. Return the best subarray found.

Code

Python

class Solution:
	def maxset(self, A: List[int]) -> List[int]:
		n = len(A)
		best = []
		for i in range(n):
			for j in range(i, n):
				if all(x >= 0 for x in A[i:j+1]):
					s = sum(A[i:j+1])
					if (not best or s > sum(best) or
						(s == sum(best) and (j-i+1 > len(best) or
						(j-i+1 == len(best) and i < A.index(best[0]))))):
						best = A[i:j+1]
		return best

Complexity

• ⏰ Time complexity: O(n^3) — All subarrays are checked and each is validated for non-negativity.
• 🧺 Space complexity: O(1) — Only a few variables are used.

Method 2 – Linear Scan

Intuition

Scan the array once, tracking the current non-negative segment and updating the best segment found so far using the required tiebreakers.

Approach

1. Initialize variables to track the best segment (sum, length, start index) and the current segment.
2. Iterate through the array:
   • If the current element is non-negative, add it to the current segment.
   • If it is negative, reset the current segment.
   • After each update, check if the current segment is better than the best so far (using sum, then length, then start index).
3. Return the best segment found.

Code

C++

class Solution {
public:
	vector<int> maxset(vector<int> &A) {
		long maxSum = -1, sum = 0;
		int start = 0, bestStart = -1, bestLen = 0, len = 0;
		for (int i = 0; i < (int)A.size(); ++i) {
			if (A[i] >= 0) {
				sum += A[i];
				len++;
				if (sum > maxSum || (sum == maxSum && len > bestLen)) {
					maxSum = sum;
					bestStart = start;
					bestLen = len;
				}
			} else {
				sum = 0;
				len = 0;
				start = i + 1;
			}
		}
		if (bestStart == -1) return {};
		return vector<int>(A.begin() + bestStart, A.begin() + bestStart + bestLen);
	}
};

Java

class Solution {
	public ArrayList<Integer> maxset(ArrayList<Integer> A) {
		long maxSum = -1, sum = 0;
		int start = 0, bestStart = -1, bestLen = 0, len = 0;
		for (int i = 0; i < A.size(); i++) {
			if (A.get(i) >= 0) {
				sum += A.get(i);
				len++;
				if (sum > maxSum || (sum == maxSum && len > bestLen)) {
					maxSum = sum;
					bestStart = start;
					bestLen = len;
				}
			} else {
				sum = 0;
				len = 0;
				start = i + 1;
			}
		}
		ArrayList<Integer> ans = new ArrayList<>();
		if (bestStart == -1) return ans;
		for (int i = bestStart; i < bestStart + bestLen; i++) ans.add(A.get(i));
		return ans;
	}
}

Python

from typing import List
class Solution:
	def maxset(self, A: List[int]) -> List[int]:
		max_sum = -1
		sum_ = 0
		start = 0
		best_start = -1
		best_len = 0
		len_ = 0
		for i, x in enumerate(A):
			if x >= 0:
				sum_ += x
				len_ += 1
				if sum_ > max_sum or (sum_ == max_sum and len_ > best_len):
					max_sum = sum_
					best_start = start
					best_len = len_
			else:
				sum_ = 0
				len_ = 0
				start = i + 1
		if best_start == -1:
			return []
		return A[best_start:best_start+best_len]

Complexity

• ⏰ Time complexity: O(n) — The array is scanned once.
• 🧺 Space complexity: O(1) — Only a few variables are used.