# Not elegant but easy to understand (15ms)

• The idea is to calculate the maximum profit (unlimited transactions), then reduce the number of transactions by either deleting or combing transactions.

``````class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size()<=1 || k==0)
return 0;
vector<int> lowPrices;
vector<int> highPrices;
for(int i=0; i<prices.size(); ++i){
if((i==0 && prices[i] < prices[i+1]) || (i>0 && i<prices.size()-1 && prices[i]<=prices[i-1] && prices[i+1] >prices[i])){
if(lowPrices.size() == highPrices.size())
lowPrices.push_back(prices[i]);
}
if((i==prices.size()-1 && prices[i] >= prices[i-1]) || (i>0 && i<prices.size()-1 && prices[i]>=prices[i-1] && prices[i+1] < prices[i])){
if(lowPrices.size() > highPrices.size())
highPrices.push_back(prices[i]);
}
}
int profit = 0;
for(int i=0; i<lowPrices.size(); ++i)
profit += highPrices[i] - lowPrices[i];
if(k >= lowPrices.size() || profit == 0)
return profit;
int count = lowPrices.size() - k;
//either delete some transactions or combine neighbor transactions
while(count > 0){
int delLoss = INT_MAX;
int delIndex;
int comLoss = INT_MAX;
pair<int, int> comPair;
for(int i=0; i<lowPrices.size(); ++i){
if(lowPrices[i]!=-1 && highPrices[i]-lowPrices[i]<delLoss){
delIndex = i;
delLoss = highPrices[i]-lowPrices[i];
}
if(lowPrices[i] != -1){
int j = i+1;
while(j<lowPrices.size() && lowPrices[j] == -1)
++j;
if(j<lowPrices.size() && (highPrices[i]-lowPrices[j] < comLoss)){
comLoss = highPrices[i]-lowPrices[j];
comPair.first = i;
comPair.second = j;
}
}
}
if(delLoss <= comLoss){
lowPrices[delIndex] = -1;
profit -= delLoss;
}
else{
highPrices[comPair.first] = highPrices[comPair.second];
lowPrices[comPair.second] = -1;
profit -= comLoss;
}
--count;
}
return profit;
}
};``````

• I love this idea. It's easy to understand.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.