Can anyone tell me why this method can be accepted?


  • 0
    N
     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=1; j<=k; ++j){
                rele[j] = max(rele[j],hold[j] + cur);
                hold[j] = max(hold[j],rele[j-1] - cur);
            }
        }
        return rele[k];  
    }
    

    The last few steps:

           for(int j=1; j<=k; ++j){
                rele[j] = max(rele[j],hold[j] + cur);
                hold[j] = max(hold[j],rele[j-1] - cur);
            }
    

    My opinion is j is supposed to be started with k and ended up with 1, like code below:

            for(int j=k; j>0; --j){
                rele[j] = max(rele[j],hold[j] + cur);
                hold[j] = max(hold[j],rele[j-1] - cur);
            }
    

    However, the perious one get accepted. I'm comfused, Can anyone make it through?


  • 0
    L

    I know your opinion is that if use for(int j=k; j>0; --j) then each time we update rele[j] and hold[j], the values in max(rele[j],hold[j] + cur) was got from previous iteration. This makes sense and is very straightforward thinking for DP. The reason why for(int j=1; j<=k; ++j) works as well is that we could consider it as "buy and sell stock at the same day". Take this fomular hold[j] = max(hold[j],rele[j-1] - cur) as example, rele[j-1] would be got from the current iteration of day i, so there are two cases: 1st one is sell stock on day i and get rele[j-1], 2nd one is didn't sell stock on day i, rele[j-1] is same as the value in previous iteration day i-1. In case 2 it's no difference than the normal form, in case 1 we just consider rele[j-1]-cur as buy stock at day i and sell it right away, compare it with hold[j] and choose the bigger one.


Log in to reply
 

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