AlgoViz
HomeArrays & Hashing

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

Medium

Kadane, remembering where the run began

Problem

Find the contiguous subarray with the largest sum and also print the subarray itself.

In simple words

Track a running sum, restart it when it goes negative, and remember where the best run sat.

The idea

Run Kadane's algorithm but also track the index where the current run started, and snapshot start and end whenever a new best appears. The reset point of the running sum is exactly the start of a new candidate subarray.

The trick

  • Set the tentative start when the running sum resets to zero.
  • Commit start and end only when the best actually improves.
-2
1
-3
4
-1
2
1
-5
4
0
1
2
3
4
5
6
7
8

Step 1 of 47. Brute force: add up every subarray and keep the biggest sum. Values: -2, 1, -3, 4, -1, 2, 1, -5, 4.

1/47
Brute force
timeO(n²)spaceO(1)

Sum every subarray.

1let best = -Infinity;2for (let i = 0; i < n; i++) {3  let sum = 0;4  for (let j = i; j < n; j++) { sum += nums[j]; best = Math.max(best, sum); }5}

Input

array
[-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

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

Example 2

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

Example 3

Input:
nums = [-3, -1, -2]
Output:
-1
Explanation:
All negative, so pick the least-bad single -1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.