Maximum Score from Singles, Pairs and Triples
Autumn Tournament (2009)
Submission name: triples.cpp
Problem summary
Partition the input integers into groups of one, two or three. A group contributes the product of its elements. Maximize the sum of all group contributions; every input element must be used exactly once.
Source clarification. The sorted-end DP follows the official editorial’s exchange argument: https://infos.infosbg.com/files/Contests/ETI/2009/C/analyses/triples_analysis.pdf
Input
N, followed by N signed integer values.
Output
The maximum obtainable sum.
Constraints
1<N≤1000; −30000≤Ai≤30000.
Worked example
Original statement sample.
Input
7 0 2 -1 2 7 -3 -4
Output
88
Solution analysis
- Sort the values. The official solution uses an exchange property: an optimal grouping can be built by repeatedly taking one to three values from the two ends of the remaining sorted interval. Large positive factors favor other large factors, while large-magnitude negatives favor pairing with negatives; mixing signs is covered by taking values from both ends.
- Let dp[left][right] be the best score obtainable from that inclusive interval; an empty interval has score zero. For group size s=1,2,3, try taking a values from the left and s−a from the right. Multiply those chosen values and add the optimum for the smaller interval. There are only 2+3+4=9 choices per state.
- Process intervals in increasing length so every smaller subproblem is available. No separate greedy sign cases are necessary: the DP also handles ones, zeros and leftover negatives. Use long long before multiplying, because a product of three values can reach 27000000000000.
- For the sample, take (−4,−3,7), (−1,0), (2), (2). Their contributions are 84,0,2,2, totaling 88. All seven values are used. Simply grouping consecutive sorted triples would miss this mixed-end choice.
Why it works
The sorted-end exchange property used in the official editorial ensures that at least one optimal grouping has a next group drawn from the two extremes of the remaining sorted list. The recurrence enumerates every allowed size and every distribution between these extremes. After removing the chosen group, the remaining values form a smaller interval; induction on interval length shows that the recurrence returns its optimum, and hence the optimum for the whole list.
Watch out. All elements must be consumed, including negative values. Group multiplication must use 64-bit operands. Include mixed-end triples, not only three adjacent sorted values. The optimization relies on group size at most three.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<long long>values(n);
for(long long&value:values){
cin>>value;
}
sort(values.begin(),values.end());
vector<vector<long long>>dp(n,vector<long long>(n,0));
for(int length=1;length<=n;length++){
for(int left=0;left+length<=n;left++){
int right=left+length-1;
long long best=numeric_limits<long long>::lowest();
for(int size=1;size<=min(3,length);size++){
for(int takeLeft=0;takeLeft<=size;takeLeft++){
int takeRight=size-takeLeft;
long long product=1;
for(int i=0;i<takeLeft;i++){
product*=values[left+i];
}
for(int i=0;i<takeRight;i++){
product*=values[right-i];
}
int nextLeft=left+takeLeft;
int nextRight=right-takeRight;
long long remaining=nextLeft<=nextRight?dp[nextLeft][nextRight]:0;
// Enumerate every split of this group between the two ends.
best=max(best,product+remaining);
}
}
dp[left][right]=best;
}
}
cout<<dp[0][n-1]<<'\n';
}