Maximum Product
National Olympiad — Municipal round (2019 season)
Submission name: product.cpp
Problem summary
Given positive heights a1,…,an, maximize (j−i)·min(ai,aj) over i<j.
Input
n, then n heights.
Output
The maximum product.
Constraints
1 < n < 500,000; 0 < ai < 100,000.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
4 1 5 4 3
Output
6
Solution analysis
- Start with the widest pair, left=0 and right=n−1. Evaluate its width times the smaller endpoint height. Then discard the endpoint with smaller height, choosing either endpoint on a tie.
- If a[left]≤a[right], every pair using left and an interior right endpoint has smaller width and minimum height at most a[left]. None can exceed the pair just evaluated. Thus removing left cannot discard an unaccounted-for optimum. The symmetric argument applies when the right endpoint is smaller.
- For heights 1,5,4,3 the outer pair gives 3. Discard height 1, then the pair at indices 2 and 4 gives 2·3=6. Discard the right endpoint, inspect the remaining pair with product 4, and keep the maximum six.
Why it works
At each step all pairs discarded with the shorter endpoint are bounded above by the current evaluated pair. Any global optimum is therefore either already matched by the recorded maximum or still lies between the remaining pointers. When the pointers meet no pairs remain, so the maximum recorded is globally optimal.
Watch out. Use 64-bit multiplication: the product may exceed a signed 32-bit integer. Move the smaller height, not the larger one.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: At each step all pairs discarded with the shorter endpoint are bounded above by the
// current evaluated pair. Any global optimum is therefore either already matched by the recorded
// maximum or still lies between the remaining pointers.
#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>a(n);
for(int&value:a){
cin>>value;
}
int left=0,right=n-1;
long long answer=0;
while(left<right){
answer=max(answer,1LL*(right-left)*min(a[left],a[right]));
if(a[left]<=a[right]){
++left;
}
else{
--right;
}
}
cout<<answer<<'\n';
}