My O(nk) C++ concise solution


  • 0
    F
    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if(k==0) return 0;
            if (k>=prices.size()/2) {
                int res = 0;
                for (int i = 0; i< (int)prices.size()-1; i++) res += ((prices[i+1]>prices[i])?(prices[i+1]-prices[i]):0);
                return res;
            }
            
            vector<int> buy(k, INT_MIN);
            vector<int> sell(k, 0);
            
            for (auto i:prices) {
                for (int j=0; j < k; j++) {
                    buy[j] = max(buy[j], ((j==0)?0:sell[j-1])-i);
                    sell[j] = max(sell[j], buy[j]+i);
                }
            }
            
            return sell[k-1];
        }
    };
    
    1. if(k>=prices.size()/2), we can buy and sell each time it is profitable.
    2. We use buy[j] and sell[j] to record how much money we have after j buys and j sells. Here we suppose the initial money amount is 0. The transition function is: buy[j] = max(buy[j], sell[j-1]-prices[i]) and sell[j] = max(sell[j], buy[j]+prices[i]).

Log in to reply
 

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