Peak sum during restricted jumps
National Olympiad — National round
Submission name: jumps.cpp
Problem summary
Start at the first element with a running sum equal to it. Move right by one or two positions, adding each landed-on element. Two length-2 jumps cannot be consecutive; eventually the route must end exactly at the last element. Maximize the running sum attained at ANY point of such a route, not necessarily at its end.
Input
N, followed by N integers.
Output
The maximum running sum attainable during a valid complete route.
Constraints
1 < N < 100,000; −99 ≤ a[i] ≤ 99.
Worked example
An independently prepared example for this explanation.
Input
4 4 -2 7 -20
Output
11
Solution analysis
- Let one[i] and two[i] be the best arrival sums according to the last jump length.
- one[i]=max(one[i−1],two[i−1])+a[i]; two[i]=one[i−2]+a[i]. Treat the starting state as one[0]=a[0].
- Take the maximum over every reachable state, including the start. Any prefix extends to the last position with length-1 jumps.
Why it works
The transitions cover exactly legal jumps. Every reachable prefix can be completed, so the largest prefix sum across all states is precisely the requested peak.
Watch out. Returning only the best sum at the final element solves a different, easier-to-misread objective. Do not allow consecutive double jumps.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The transitions cover exactly legal jumps. Every reachable prefix can be completed, so the
// largest prefix sum across all states is precisely the requested peak.
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
int main(){
int n;
cin>>n;
vector<long long>a(n),one(n,LLONG_MIN/4),two=one;
for(auto&x:a){
cin>>x;
}
one[0]=a[0];
long long ans=a[0];
for(int i=1;i<n;i++){
one[i]=max(one[i-1],two[i-1])+a[i];
if(i>=2){
two[i]=one[i-2]+a[i];
}
ans=max({ans,one[i],two[i]});
}
cout<<ans<<'\n';
}