public int maxProfit(int[] prices) {
if(prices.length == 0  prices.length == 1) return 0;
int[] maxProfit = new int[prices.length];
maxProfit[0]=0;
maxProfit[1]=Math.max(0, prices[1]prices[0]);
int value = Math.max(0prices[0],0prices[1]);
for(int i = 2; i<prices.length; i++) {
int temp = prices[i]+value;
if(temp <= maxProfit[i1]) maxProfit[i] = maxProfit[i1];
else maxProfit[i] = temp;
if(maxProfit[i2]prices[i]>value) value = maxProfit[i2]prices[i];
}
return maxProfit[prices.length1];
}
Share my 3ms Java DP solution


Awesome!
I change a little bit for your reference.
public int maxProfit(int[] p) { if(p.length == 0  p.length == 1) return 0; int n = p.length; int[] dp = new int[n]; dp[0] = 0; dp[1] = Math.max(0, p[1]  p[0]); int buy = Math.max(0  p[0], 0  p[1]); for(int i = 2; i < n; i++) { dp[i] = Math.max(dp[i  1], p[i] + buy); buy = Math.max(buy, dp[i  2]  p[i]); } return dp[n  1]; }

Sorry, just saw your post. The variable buy means, if I buy the stock at this time the highest profit I could make. Initially, the buy should be the bigger one in 0  p[0], 0  p[1]. And during the iteration, the buy equals the most profit I could make if I buy the stock at this time or not. If I buy the stock at i, the buy should be dp[i  2]  p[i], because the dp[i  2] means the highest profit I can make at time i  2, and I spent p[i] to buy the stock. So for example, At time i, the dp[i] could be dp[i  1] means I did nothing, or be p[i] + buy means I bought the stock several days before and sell it at i.