DP, O(KN) Time,O(n) Space, cpp , solution.


  • 18
    I

    if k >= n/2, we can have transactions any time, it can be solved by O(n).

    else, we can do it in DP.

    use dp[k][i+1] represents, The max profit of using [0,i] data and k transactions.

    So we have:

    dp[k][i+1] = max(dp[k-1][i+1], dp[k][i], max( dp[k-1][j] + prices[i] - prices[j] ))

    = max(dp[k-1][i+1], dp[k][i], prices[i] + max( dp[k-1][j] - prices[j] )) { 0 <= j < i }

    it can be solved by O(kn).

    The Code:

    class Solution {
    public:
        int maxProfit_all(vector<int> &prices) {
            int n = prices.size();
            int sum = 0;
            for(int i = 1;i < n;i++){
                if(prices[i] > prices[i-1]){
                    sum += prices[i] - prices[i-1];
                }
            }
            return sum;
        }
        int maxProfit(int k, vector<int> &prices) {
            int n = prices.size();
            if(k >= n/2){
                return maxProfit_all(prices);    
            }
            int dp[2][n+1];
            memset(dp,0,sizeof(dp));
            for(int t = 1; t <= k; t++){
                int cur_max = 0x80000000;
                dp[t%2][0] = 0;
                for(int i = 0; i < n; i++){
                    dp[t%2][i+1] = max(dp[(t+1)%2][i+1],max(dp[t%2][i],prices[i] + cur_max));
                    cur_max = max(cur_max,dp[(t+1)%2][i] - prices[i]);
                }
            }
            return dp[k%2][n];
        }
    };

  • 2
    F

    thank you very much, i think the key insight is
    max( dp[k-1][j] - prices[j] ))
    can be kept in a tmp value when we loop through i


  • 0
    J
    This post is deleted!

  • 6
    J

    Do some improvement base on your solution.
    Just consider the peak value in prices. So build a new vector, peaks, only contains the peak values in prices.
    Then use the same algorithm on peaks instead of prices.

    The Codes:

    class Solution {
    public:
        int maxProfit(int k, vector<int> &prices) {
            int res=0,n=prices.size(),maxTrans=0;
            if(n==0)return 0;
            vector<int>peak;
            for(int i=1;i<n;++i)
                if(prices[i]>prices[i-1])res+=prices[i]-prices[i-1];
                
            peak.push_back(prices[0]);
            for(int i=1;i<prices.size()-1;++i)
                if((prices[i-1]<=prices[i] && prices[i]>prices[i+1])||(prices[i-1]>=prices[i] && prices[i]<prices[i+1]))
                    peak.push_back(prices[i]);
            if(n>1)peak.push_back(prices[n-1]);
            
            if(k>=peak.size()/2)return res;
            int n1 = peak.size();
            int dp[2][n1+1];
            memset(dp,0,sizeof(dp));
            for(int t = 1; t <= k; t++){
                int cur_max = 0x80000000;
                dp[t%2][0] = 0;
                for(int i = 0; i < n1; i++){
                    dp[t%2][i+1] = max(dp[(t+1)%2][i+1],max(dp[t%2][i],peak[i] + cur_max));
                    cur_max = max(cur_max,dp[(t+1)%2][i] - peak[i]);
                }
            }
            return dp[k%2][n1];
        }
    };

  • 0
    I

    Thanks for the nice improvement.


  • 0
    Y

    There is a more clean and concise cpp solution.When k<size/2:Time complexity is O(kn), space complexity can be O(n) because this DP only uses the result from last step:

    class Solution {
    public:
        int maxProfit(int k, vector<int> &prices) {
            int size = (int)prices.size();
            if (k==0||size<2) {
                return 0;
            }
            if (k>size/2) {
                int sum = 0;
                for(int i = 1;i < size;i++){
                    if(prices[i] > prices[i-1]){
                        sum += prices[i] - prices[i-1];
                    }
                }
                return sum;
            }
            vector<int> buy(k,INT_MIN);
            vector<int> sell(k,0);
            for (int i=0; i<size; i++) {
                for (int j=k-1; j>=0; j--) {
                    sell[j]=max(sell[j],buy[j]+prices[i]);
                    buy[j]=max(buy[j],(j>0?sell[j-1]:0)-prices[i]);
                }
            }
            return sell[k-1];
        }
    };

  • 0
    C

    Could you please explain more about the code? Thanks


  • 0

  • 0
    D

    Good improvement since there will be a better chance to have k >= peak.size/2 and use the simple method.

    Though I think the calculation of res should be put inside the if block, you don't need to do this for other cases.


  • 0
    A

    Hi, Insulator. I confuse that why you omit to compute "max( dp[k-1][j] - prices[j] ) { 0 <= j < i }" like loop, and compute the cur_max "cur_max = max(cur_max,dp[(t+1)%2][i] - prices[i]);" directly. Is there any special idea? thanks.


  • 7
    T

    I modified the code from @yulingtianxia a little for better understanding.

    Basically, in the k-th iteration:

    buy[k][i] represents the maximum profit if you buy the stock on day i after at most k - 1 transactions.

    buy[k][i] = max(buy[k - 1][i], sell[k - 1][i - 1] - prices[i])
    

    sell[k][i] represents the maximum profit if you sell the stock on day i after at most k - 1 transactions.

    sell[k][i] = max(sell[k - 1][i], buy[k - 1][i - 1] + prices[i])
    

    we can reuse the buy[i - 1] and sell[i - 1] as buy[i] and sell[i].

    The code:

    class Solution {
    public:
        int maxProfit(int k, vector<int> &prices) {
            int N = prices.size();
            if (k == 0 || N < 2) return 0;
            
            if (k > N / 2) {
                int sum = 0;
                for (int i = 1; i < N; i++){
                    if (prices[i] > prices[i - 1]){
                        sum += prices[i] - prices[i - 1];
                    }
                }
                return sum;
            }
            
            vector<int> buy(k + 1, INT_MIN);
            vector<int> sell(k + 1, 0);
            for (int i = 0; i< N; ++i) {
                for (int j = 1; j <= k; ++j) {
                    buy[j] = max(buy[j], sell[j - 1] - prices[i]);
                    sell[j] = max(sell[j], buy[j] + prices[i]);
                }
            }
            return sell[k];
        }
    };

Log in to reply
 

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