MediumCoding

Maximum Subarray

Asked at

Blinkit

Oracle

Wells Fargo

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Track the best non-empty subarray sum ending at the current index.
02Choose between starting at the current value and extending the previous ending sum.
03Keep the greatest ending sum seen anywhere as the result.
04Initialize from the first value to handle all-negative arrays.

Reference answer

Initialize ending and best to the first value. For each later value x, set ending = max(x, ending + x): an optimal subarray ending here either starts here or extends the optimal subarray ending one position earlier. Then update best = max(best, ending). This examines the best candidate for every possible final index, so it covers every non-empty contiguous subarray. Initialization from the first value is important because an all-negative array must return its largest element, not zero. The algorithm runs in O(n) time and uses O(1) extra space. If the actual subarray is required, track a tentative start when the algorithm chooses x, and save the start and current end whenever best improves. Divide-and-conquer is possible in O(n log n) but is unnecessary here.

Then expect these follow-ups

How would you return the subarray itself?
Tests: reconstruction
How does the circular-array variant differ?
Tests: variant reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question