Two Pairs of Candy
National Olympiad — National round (2013 season)
Submission name: dream.cpp
Problem summary
Choose two disjoint adjacent pairs of candy packets in a line. Maximize the total candies in the four chosen packets. The two pairs may touch each other.
Input
N, followed by N positive packet counts.
Output
The maximum total candies from two disjoint adjacent pairs.
Constraints
4 ≤ N ≤ 10,000; 1 ≤ each count ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
8 3 8 5 2 1 7 8 5
Output
28
Solution analysis
- Let pairSum[i]=a[i]+a[i+1]. If the right pair begins at j, the left pair must start no later than j−2.
- Scan right-pair starts j from 2 onward. Maintain the largest pair sum whose start is at most j−2, then combine it with pairSum[j]. This avoids checking all pair combinations.
- In the sample, packets 8,5 form a pair totaling 13 and packets 7,8 form another totaling 15. Together they give 28.
Why it works
For each right start j, the maintained maximum covers exactly all disjoint left pairs, and therefore gives the best solution with that right pair. Every feasible selection has some right start, so maximizing these candidates finds the global optimum.
Watch out. Adjacent pairs must not share a packet. Allow start indices differing by exactly two. Choosing the two largest pair sums independently may overlap.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> candies(n);
for (long long &count : candies) {
cin >> count;
}
long long bestLeft = 0;
long long answer = 0;
for (int right = 2; right + 1 < n; right++) {
// The newest allowed left pair ends just before the right pair.
bestLeft = max(bestLeft, candies[right - 2] + candies[right - 1]);
answer = max(answer, bestLeft + candies[right] + candies[right + 1]);
}
cout << answer << '\n';
}