Not elegant but easy to understand (15ms)


  • 3
    F

    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;
            }
        };

  • 1
    J

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


Log in to reply
 

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