# Dp solution,c++ 4ms

• 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;
}
};``````

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

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