Maximum Consecutive Sum
National Olympiad — Regional round (2014 season)
Submission name: sum.cpp
Problem summary
Choose one or more consecutive numbers from a sequence to maximize their sum.
Input
n, followed by n integers in sequence order.
Output
The maximum nonempty consecutive sum.
Constraints
2≤n≤1000000; −100<a[i]<100.
Worked example
An independently prepared example for this explanation.
Input
4 4 5 -3 1
Output
9
Solution analysis
- Maintain ending, the maximum sum of a nonempty segment ending at the current position. For a new value x, either start a new segment or extend the previous best: ending=max(x,ending+x).
- Keep the largest ending encountered as the answer. Initialize both variables to the first input value, ensuring all-negative sequences still select one number rather than an empty segment.
- For 4,5,−3,1 the ending values are 4,9,6,7. The maximum is 9, achieved by the first two cards.
Why it works
Every segment ending at the current position either consists only of x or extends a segment ending immediately before it. The recurrence optimizes both cases, so induction proves ending correct. Every nonempty segment has a right endpoint, and the maximum over all endpoints is the global optimum.
Watch out. The chosen segment must be nonempty. Initializing the answer to zero incorrectly handles all-negative input.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
// Algorithm: Maintain ending, the maximum sum of a nonempty segment ending at the current
// position.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count,value;
cin>>count>>value;
int ending=value;
int answer=value;
for(int i=1;i<count;i++){
cin>>value;
ending=max(value,ending+value);
answer=max(answer,ending);
}
cout<<answer<<'\n';
}