Medium–hard · one pass, one idea
Maximum Subarray Sum
Out of all the contiguous stretches of the array, which one has the biggest sum? The brute force is O(n²). The insight is one sentence long.
At a glanceKadane's algorithm — running = max(a[i], running + a[i]) and best = max(best, running); it stays correct on all-negative arrays because the stretch must be non-empty.
Problem
Input: The first line is an integer n (1 ≤ n ≤ 1000). The second line holds n integers separated by spaces (−1000 ≤ ai ≤ 1000). The numbers may be negative.
Output: The largest possible sum of a non-empty contiguous stretch.
Samples:
| Input | Output |
|---|---|
8 | 6 |
5 | -1 |
1 | 5 |
In the first sample the best stretch is 4 -1 2 1 = 6. In the second, every number is negative, so you must still pick one — the answer is −1, not 0. That case is where most solutions break.
Your solution
Custom input for "Run my input"
Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.
Stuck? Hints
Hint 1 — The brute force first, so you can feel the waste
Try every start i, every end j, sum the range, keep the max. That's O(n²) — for n = 1000 it's about a million additions, and most of them are recomputing sums you already had. The fast solution never looks backwards.
Hint 2 — One running total is enough
Keep cur = the best sum of a stretch ending at the current position. When the next number x arrives you have exactly two choices: extend the run (cur + x) or start a new run at x. Take the larger. Then update best if cur beat it.
Hint 3 — The one-sentence insight
If cur is negative, it can only drag the next number down — so throw it away and start fresh. That's it: if (cur < 0) cur = x; else cur = cur + x;. Everything else is bookkeeping.
Solution (try it first!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int best, cur;
cin >> best;
cur = best;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if (cur < 0) cur = x;
else cur = cur + x;
if (cur > best) best = cur;
}
cout << best << endl;
return 0;
}This is Kadane's algorithm, and it's the standard introduction to dynamic programming: cur is a state that summarises everything you need to know about the past in one number. You didn't remember the array — you remembered the one thing that matters. That reframing, "what is the minimum I must carry forward?", is the entire discipline. And it's the last problem in the chain — you've now covered input, loops, arrays, strings, bits, sorting, searching and one real algorithm. Go back through the list and see how many you can do without hints.
Deep dive
Why this works
Keep cur = the best sum of a stretch ending right here. When the next number arrives you have two choices: extend the run, or start a new one at it. Take the larger.
The cost
O(n) in one pass with two extra variables. Enumerating every range is O(n²) — and most of those additions recompute sums you already had.
Where it goes wrong
- Starting
bestat 0 prints 0 for all-negative input, but the empty stretch is not allowed — the answer is the largest negative number. - Deciding with
if (x > 0)instead ofif (cur < 0)extends a negative run that should have been abandoned, and the maximum comes out too low.
Next step
That's the end of the chain. Look back at the first problem — you have come a long way.
Two things to remember
- A negative running total only drags you down — drop it and restart at the current number.
- The core question of dynamic programming: what is the least I must carry forward?
🐞 This version fails — open it and try
best starts at 0 — all-negative input gives 0, but the empty stretch is not allowed
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int best = 0, cur = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (cur < 0) cur = x;
else cur = cur + x;
if (cur > best) best = cur;
}
cout << best << endl;
return 0;
}