# Share my 3ms Java DP solution

• ``````    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(0-prices[0],0-prices[1]);
for(int i = 2; i<prices.length; i++) {
int temp = prices[i]+value;
if(temp <= maxProfit[i-1]) maxProfit[i] = maxProfit[i-1];
else maxProfit[i] = temp;

if(maxProfit[i-2]-prices[i]>value) value = maxProfit[i-2]-prices[i];
}
return maxProfit[prices.length-1];
}``````

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

• Nice. I didn't realize "value" in original post actually meant the largest profit when we bought at ith day until I saw the name of your variables. Thanks!

• Could you please provide some more explanation? About the calculation of 'buy' for the first time and each dp[i] ?

• 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.

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