Interactive Lab · DSA & Algorithms
Daily profit and loss for a stock, some days up, some down. Two questions every interviewer asks. “What was the total from day l to day r?” Adding it up each time is O(n) per question; precompute prefix sums once and every answer is P[r+1] − P[l], a single subtraction. “Which stretch of days made the most money?” Trying every (start, end) pair is O(n²). Kadane's algorithm does it in one pass with one rule: if the running sum goes negative, drop it and start fresh, because a negative head start only drags down whatever comes next.
▶ Setup, the array
Values −9 … 9, up to 14 of them. Type your own (press Enter or tab out), negatives welcome.
▶ Part 1, prefix sums: any range sum in O(1)
▶ Part 2, Kadane: the best subarray in one pass
Top: the array. The dashed orange box is the window Kadane is currently extending; the green box is the best window so far. Bottom: the running sum cur after each index. When it dips below zero, the next step throws it away (↺ reset).
Prefix sums are everywhere data is aggregated: a dashboard's “revenue between two dates” reads two cumulative totals, image filters use 2-D prefix sums (summed-area tables) to blur in O(1) per pixel, and Subarray Sum Equals K is prefix sums plus a hashmap. Kadane is the classic first DP-in-disguise: best-profit stretches, the strongest signal segment in a noisy series, and Best Time to Buy and Sell Stock (Kadane on day-to-day price differences). Both are the same idea as the sliding window: carry a running sum instead of recomputing it.
The code that's actually running, build prefix sums once, sweep Kadane once
Press − all negative before you step. Predict: what does Kadane return when every number is negative, 0 (the empty subarray) or the largest single element? This version answers the non-empty question: it resets before adding a[i], so cur always holds at least one element and the answer is the least-negative number. The popular shortcut “add, then reset to 0 if negative” returns 0 here, the classic wrong answer. Then compare the counters at the end: Kadane takes n steps, brute force checks n(n+1)/2 subarrays. At n = 14 that's 14 vs 105; at n = 10⁵ it's the difference between instant and a timeout.
The takeaway
P[0] = 0, P[k+1] = P[k] + a[k]. Then sum(a[l..r]) = P[r+1] − P[l]: everything before l cancels. Build is O(n), every query is O(1). Note the off-by-one: P has n+1 entries.l ≤ r maximising P[r+1] − P[l]. Kadane is just that, done cleverly: keep the lowest P seen so far and measure each new P against it.O(n) time, O(1) space.O(n³), brute force with prefix sums is O(n²), Kadane is O(n). Same answer, each step reusing more of the work already done.