Dp solution,c++ 4ms


  • 2
    Y

    The problem could be converted to a problem of Maximal sequence.
    The prices[N] we have, the profit[i]=prices[i+1]-prices[i] we could get.
    The assitpf[i] is used to record the maximal sequence including profit[i].

    The maximum profit is the maximal sequence, the limitation of "After you sell your stock, you cannot buy stock on next day" means that assitpf[i]=profit[i]+assit[i-2] is forbidden.

    For example:

    prices=1 2 3 0 2 1 6 5

    profit= 1 1 -3 2 -1 5 -1

    assitpf=1 2 -1 3 2 x

    x(assitpf[i])=profit[i]+max(0,assitpf[i-1],max(assitpf[0]->assitpf[i-3]))

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
    		int len=prices.size();
    		if(len<2)return 0;
    		if(len==2)return max(0,prices[1]-prices[0]);
    		len--;
    		vector<int> profit(len,0);
    		vector<int> assitpf(len,0);
    		for(int i=0;i<len;i++)
    			profit[i]=prices[i+1]-prices[i];
    		int maxp=0,prev2max=0;
    		for(int i=0;i<len;i++){
    			if(i>=3)
    				prev2max=max(prev2max,assitpf[i-3]);
    			if(i==0){
    				assitpf[i]=max(profit[i],0);
    				maxp=assitpf[i];
    			} else{
    				assitpf[i]=profit[i]+max(assitpf[i-1],max(prev2max,0));
    				maxp=max(maxp,assitpf[i]);
    			}
    		}
    		return maxp;
        }
    };

  • 0
    W

    nice reduction, I assume its the best thought so far :)
    BTW, array of profit is dispensable


Log in to reply
 

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