O(n) time+O(n)space


  • 0
    P
    typedef vector<int> vi;
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.empty()) return 0;
            int n = (int)prices.size();
            vi prof(n,0);
            for(int r=0;r<2;++r){
                for(int i=1,m=prof[0]-prices[0];i<n;++i){
                    m = max(m,prof[i]-prices[i]);
                    prof[i] = max(prof[i-1],prices[i]+m);
                }
            }
            return prof[n-1];
        }
    };
    

    The prof vector is storing the profit. prof[i] the maximum profit a person can get up to the ith day with at most r+1 transactions. And iterate r from 0 to 2-1.


  • 0
    C

    what does m means


  • 0
    P

    @chjxiao Sorry for the late reply.
    Since in the (r-1)th outer loop: prof[i] is the maximum profit a person can get up to the ith day with at most (r) transactions. Then for the (r)th loop: we want to update prof[i] s.t. it is becomes the maximum profit one can get up to the ith day with at most (r+1) transactions. So actually we are maximizing the following:

    prof[i] = max(prof[i-1] , max_{j: 1->i} (price[i] - price[j] + prof[j]) )
    

    The first term in the max function is easy to deal with. For the second term max_{j: 1->i} (price[i] - price[j] + prof[j]), we are tracking the maximum value of - price[j] + prof[j] during the loop, which is the m in the code. Since price[i] is fixed.


Log in to reply
 

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