Maintained by Vikas Dulgunde, software engineer
You are handed an array of integers that may mix positive and negative values. A subarray is any block of consecutive elements taken from the array without skipping or reordering. Your job is to look across every possible block and report the single highest total any of them can reach.
The block must contain at least one element, so you can never return an empty selection. When every value is negative the best you can do is pick the one element closest to zero, since adding more numbers only drags the total down further.
Return just the maximum sum itself, not the indices or the block of numbers that produced it. The order of the array is fixed; you only choose where a block starts and where it ends.
The block [4, -1, 2, 1] sums to 6, which beats every other contiguous run.
Taking the whole array gives 5 + 4 - 1 + 7 + 8 = 23. The single -1 is small enough that keeping it still leaves the running total ahead.
Every value is negative, so the strongest single element wins. -1 is the least bad choice.
Visible test cases
As you scan left to right, ask a local question at each index: is it better to extend the block ending just before me, or to start fresh at me?
Track a running sum for the best block that ends at the current position. If that running sum ever drops below the current element alone, throw it away and restart from the current element.
Keep a separate variable for the best total seen anywhere, and update it after computing each position's running sum. Seed both trackers with the first element so all-negative inputs are handled.
Try every start and end pair, add up the elements between them, and remember the largest sum.
The best block ending at each index is either that element alone or that element joined to the best block ending right before it. Carry that running value forward and watch the maximum.