Share my C++ DP solution with O(kn) time O(k) space, 10ms


  • 41
    H

    This is my DP solution:

    class Solution {

    public:
        int maxProfit(int k, vector<int> &prices) {
            int len = prices.size();
            if (len<2) return 0;
            if (k>len/2){ // simple case
                int ans = 0;
                for (int i=1; i<len; ++i){
                    ans += max(prices[i] - prices[i-1],0);
                }
                return ans;
            }
            int hold[k+1];
            int rele[k+1];
            for (int i=0;i<=k;++i){
                hold[i] = INT_MIN;
                rele[i] = 0;
            }
            int cur;
            for (int i=0; i<len; ++i){
                cur = prices[i];
                for(int j=k; j>0; --j){
                    rele[j] = max(rele[j],hold[j] + cur);
                    hold[j] = max(hold[j],rele[j-1] - cur);
                }
            }
            return rele[k];
        }
    

    };

    Inspired by weijiac in Best Time to Buy and Sell Stock III

    https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1


  • 2
    K

    I tried a similar solution in java but it fails to allocate heap space for one of the test cases where k = 1,000,000,000


  • 0
    D

    I met too.
    Finally I found that k should never be bigger than length of prices.
    In that case, the length is only 1000.


  • 0
    W

    test cases with k larger than prices.size()/2 would fail (don't know reason), you need to rule it out by using the method of buying stock with any number of transactions


  • 0
    K

    I think if k is large you need to DP over the length of prices than the length of k.


  • 0
    W

    Well, I think the transaction times should be <= half of the number of days(i.e. the prices). Since we need two days to finish a transaction~


  • 1
    W

    I use a vector<int> instead of your int hold[k+1] then I got a TLE...
    Maybe they just don't turn on the O2 optimization...
    After look at your code, I revised mine and got Accepted.
    Thank you for your sharing!


  • 0
    C

    I think the answer was edited after your posts, but anyhow I tried it in Java and works fine.

    http://choksheak.blogspot.com/2015/08/best-time-to-buy-and-sell-stock-iv.html


  • 0

    shouldn't the trial case be k >= n - 1 instead of n/2?
    For n days there are at most n - 1 transactions you can make.


  • 2
    A

    Acturally, do not need to let k>=n-1. If you do n-1 transactions in n days, then the prices must be non-decreasing. For n days, we do at most n/2 transactions, when the size of longest increasing sequenen is just 2. That is 1 3 1 2 1 4... , something like this. If there is an increasing sequenen which is longer than 2, we just need once transaction. Have I explained this clearly?


  • 2
    X

    I slightly change your solution to make it better understand.
    At each buy, instead of max(hold[j],rele[j-1] - cur), we actually want a lower buy price which gives: min(hold[j], prices[i]-rele[j-1]) Also, at each sell, the profit should be: max(rele[j], prices[i]-hold[j])

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            int maxProfit=0;
            
            if(prices.size()<2)
                return 0;
            if(k>prices.size()/2){
                for(int i=1; i<prices.size(); i++)
                    maxProfit += max(prices[i]-prices[i-1], 0);
                return maxProfit;
            }
            
            int hold[k+1];
            int rele[k+1];
            for (int i=0;i<=k;++i){
                hold[i] = INT_MAX;
                rele[i] = 0;
            }
            
            for(int i=0; i<prices.size(); i++){
                for(int j=k; j>=1; j--){
                    rele[j] = max(rele[j], prices[i]-hold[j]);
                    hold[j] = min(hold[j], prices[i]-rele[j-1]);
                    maxProfit=max(maxProfit, rele[j]);
                }
            }
            return maxProfit;
        }
    };
    

    At the end, thanks for your sharing, this is a wonderful solution!


  • 1
    N

    simple case is very useful for my TLE codes ...thanks


  • 0
    P

    @Aloha0424 said in Share my C++ DP solution with O(kn) time O(k) space, 10ms:

    Acturally, do not need to let k>=n-1. If you do n-1 transactions in n days, then the prices must be non-decreasing. For n days, we do at most n/2 transactions, when the size of longest increasing sequenen is just 2. That is 1 3 1 2 1 4... , something like this. If there is an increasing sequenen which is longer than 2, we just need once transaction.

    Thanks for you explination.


  • 0
    M

    Great solution!!!


  • 0

    still have trouble to figure out the logic that rele[k] is always the right answer, why not some random rele[i]? Why rele[i] is always greater than or equal to rele[i-1]?

    Maybe it's better to understand if knowing what is the meaning of rele[i].

    Thanks.


  • 0
    B

    If the test point with $k=1000000000$ is changed to $k=5000$, the answer would actually be TLE...

    I am a little confused about what the test cases are trying to test now


Log in to reply
 

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