Multipliers without adjacent threes
National Olympiad — Regional round
Submission name: seq.cpp
Problem summary
Multiply each array element by either 2 or 3 and maximize the sum. Two adjacent positions may not both receive multiplier 3.
Input
n followed by n integers, separated by whitespace.
Output
The maximum sum.
Constraints
1 ≤ n < 100,000; −9 ≤ a[i] ≤ 9.
Worked example
An independently prepared example for this explanation.
Input
3 4 -2 4
Output
20
Solution analysis
- Maintain best totals ending with multiplier 2 or multiplier 3.
- A new 2 may follow either state; a new 3 may follow only the 2 state.
- Use a negative-infinity sentinel for an impossible initial 3 state.
Why it works
The previous multiplier is all the history needed for legality. Partitioning by the last multiplier gives exhaustive, disjoint transitions.
Complexity: O(n) time and O(1) auxiliary space.
Watch out. Negative elements are allowed; choosing 3 is not always beneficial.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The previous multiplier is all the history needed for legality. Partitioning by the last
// multiplier gives exhaustive, disjoint transitions.
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int main(){
int n;
cin>>n;
long long two=0,three=LLONG_MIN/4;
while(n--){
int x;
cin>>x;
long long a=max(two,three)+2*x,b=two+3*x;
two=a;
three=b;
}
cout<<max(two,three)<<'\n';
}