Profit for Every Trade Limit
National Olympiad — National round (2025 season)
Submission name: stock.cpp
Problem summary
Given N daily prices, find the maximum profit for every limit K=1…N on the number of nonoverlapping buy-then-sell trades. A sale and the next purchase may occur on the same day. Holding more than one item at once is forbidden.
Input
N followed by N prices.
Output
N maximum profits, in increasing order of K.
Constraints
1 ≤ N ≤ 500,000; 1 ≤ price[i] ≤ 10⁹.
Worked example
An independently prepared example for this explanation.
Input
10 90 10 30 20 40 35 30 50 40 70
Output
60 70 80 90 90 90 90 90 90 90
Solution analysis
- Compress consecutive nonzero price differences of the same sign into alternating positive rises and negative falls. Discard a leading fall and a trailing fall. With no trade limit, take every positive run: their sum is the profit and their count is the number of trades.
- To reduce the allowed number of trades by one, lose the smallest absolute-valued run. If it is a positive run, discard that rise; if it is a negative run, merge the positive trades on its two sides across that fall. For an internal run, contract it and both neighbors into their signed sum. At an endpoint, delete the selected positive run and its adjacent negative run. Maintain runs in a doubly linked list and their absolute values in a min-priority queue, discarding stale entries.
- Each contraction decreases the transaction count by one and subtracts the selected absolute value from the current profit. Record the resulting profit for that count. In the example the four unrestricted rises total 90. The three cheapest successive reductions each lose 10, producing profits 80,70,60 for limits 3,2,1. Limits above the original number of rises retain 90.
Why it works
For an alternating sequence beginning and ending positively, a trade limit is the same as selecting at most that many disjoint subarrays with maximum sum. The minimum-absolute-run contraction lemma applies: when the shortest-magnitude run is positive, an optimal solution with fewer than all positive runs can be chosen to discard it or absorb it into a larger merged trade; when it is negative, an optimal solution can be chosen to merge across it or discard a neighboring positive run. Moving a neighboring boundary to make this choice costs no more, because every neighboring run has magnitude at least that of the selected run. Contracting the three runs preserves all remaining choices with the same profit offset equal to the selected magnitude; the endpoint case simply removes an unnecessary boundary fall. Thus the optimal profit with one fewer trade is exactly the old profit minus that magnitude, and the contracted instance describes every further reduction. Induction proves all recorded limits. Difference compression preserves trade profits, so these are the requested answers.
Watch out. Merge consecutive differences of the same sign before contraction. Ignore zero differences. Remove stale priority-queue entries after neighboring contractions. Store run sums and profits in 64-bit integers.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<tuple>
#include<vector>
// Algorithm: Compress consecutive nonzero price differences of the same sign into alternating
// positive rises and negative falls.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
long long previous;
cin>>previous;
vector<long long>runs;
for(int i=1;i<n;++i){
long long price;
cin>>price;
long long difference=price-previous;
previous=price;
if(difference==0){
continue;
}
if(!runs.empty()&&(runs.back()>0)==(difference>0)){
runs.back()+=difference;
}
else{
runs.push_back(difference);
}
}
if(!runs.empty()&&runs.front()<0){
runs.erase(runs.begin());
}
if(!runs.empty()&&runs.back()<0){
runs.pop_back();
}
int size=static_cast<int>(runs.size());
vector<int>left(size),right(size),version(size);
vector<bool>alive(size,true);
using Entry=tuple<long long,int,int>;
priority_queue<Entry,vector<Entry>,greater<Entry>>minimum;
long long profit=0;
int trades=0;
for(int i=0;i<size;++i){
left[i]=i-1;
right[i]=i+1<size?i+1:-1;
minimum.emplace(abs(runs[i]),i,0);
if(runs[i]>0){
profit+=runs[i];
++trades;
}
}
vector<long long>answer(n+1,profit);
while(trades>0){
auto[loss,current,stamp]=minimum.top();
minimum.pop();
if(!alive[current]||version[current]!=stamp){
continue;
}
profit-=loss;
--trades;
answer[trades]=profit;
int a=left[current];
int b=right[current];
if(a!=-1&&b!=-1){
runs[current]+=runs[a]+runs[b];
alive[a]=false;
alive[b]=false;
left[current]=left[a];
right[current]=right[b];
if(left[current]!=-1){
right[left[current]]=current;
}
if(right[current]!=-1){
left[right[current]]=current;
}
++version[current];
minimum.emplace(abs(runs[current]),current,version[current]);
}
else{
alive[current]=false;
int neighbor=a!=-1?a:b;
if(neighbor!=-1){
alive[neighbor]=false;
int outside=a!=-1?left[neighbor]:right[neighbor];
if(outside!=-1){
if(a!=-1){
right[outside]=-1;
}
else{
left[outside]=-1;
}
}
}
}
}
for(int k=1;k<=n;++k){
cout<<answer[k]<<(k==n?'\n':' ');
}
}