Equal Prefix and Suffix
National Olympiad — Municipal round (2017 season)
Submission name: suma.cpp
Problem summary
Choose nonempty disjoint prefix and suffix with equal sums, maximizing their combined number of elements.
Input
n and n positive values.
Output
Maximum combined length, or 0 if no such pair exists.
Constraints
2 ≤ n ≤ 200000; values ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
9 1 1 2 3 10 9 9 6 1
Output
6
Solution analysis
- Keep a prefix and suffix whose current endpoints never overlap, along with their sums. Start with one element on either side.
- When the sums differ, extend the side with the smaller sum. Strictly positive values mean extending the larger side cannot make that current smaller sum catch up. When sums agree, record the total length and continue extending the left side to search for longer pairs.
- The example has prefix 1+1+2+3+10+9=26 and suffix 1, which do not match, but prefix 1+1+2+3=7 and suffix 6+1=7 cover six elements. The two pointers discover this match before meeting.
Why it works
If the left sum is smaller, no suffix extension can match the current prefix, because it only increases the right sum. Thus discarding that current prefix size by extending it cannot omit a solution. The symmetric argument handles a smaller right sum. Equality is recorded before proceeding; hence all potentially optimal matches are considered.
Watch out. The two parts must not overlap and must both be nonempty. Positivity is essential to the pointer rule.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Keep a prefix and suffix whose current endpoints never overlap, along with their
// sums.
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int&value:a){
cin>>value;
}
int left=0,right=n-1,answer=0;
long long leftSum=a[left],rightSum=a[right];
while(left<right){
if(leftSum==rightSum){
answer=max(answer,left+1+n-right);
}
if(leftSum<=rightSum){
++left;
if(left<right){
leftSum+=a[left];
}
}
else{
--right;
if(left<right){
rightSum+=a[right];
}
}
}
cout<<answer<<'\n';
}