Best Split Product
National Olympiad — National round (2022 season)
Submission name: crush.cpp
Problem summary
Split a positive sequence into two nonempty contiguous parts. Maximize (sum of squared values in the first part) × (sum of values in the second part).
Input
N followed by N integers A[i], one per line.
Output
The maximum product over all N−1 splits.
Constraints
1 < N ≤ 1,000,000; 1 ≤ A[i] ≤ 100.
Worked example
An independently prepared example for this explanation.
Input
5 1 2 4 3 5
Output
168
Solution analysis
- First store the sequence and compute its total sum. Maintain a prefix sum of squares and a suffix sum of unsquared values.
- Move one element from the suffix into the prefix at each candidate split: add value² to the prefix and subtract value from the suffix. Evaluate the product after this move, stopping before the final element so both parts stay nonempty.
- For 1,2,4,3,5, splitting after 4 gives squared prefix sum 1+4+16 = 21 and suffix sum 3+5 = 8, for product 168. Other split products are 14,60,150, so 168 is maximum.
Why it works
After moving the first k elements, the two maintained sums are exactly those in the expression for the split at k. The loop visits every legal k from 1 through N−1 once. Taking their maximum therefore gives the required optimum.
Watch out. The first part uses squares; the second uses plain values. Use 64-bit multiplication before comparing products. Do not include an empty second part.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> values(n);
long long suffixSum = 0;
for (int& value : values) {
cin >> value;
suffixSum += value;
}
long long prefixSquares = 0;
long long answer = 0;
for (int i = 0; i < n - 1; i++) {
long long value = values[i];
// Move this value across the split before evaluating it.
prefixSquares += value * value;
suffixSum -= value;
answer = max(answer, prefixSquares * suffixSum);
}
cout << answer << '\n';
}