BiruLyu
8/4/2017 - 12:50 AM

## 123. Best Time to Buy and Sell Stock III(#).java

``````public class Solution {
public int maxProfit(int[] prices) {
int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
int release1 = 0, release2 = 0;
for(int i:prices){                              // Assume we only have 0 money at first
release2 = Math.max(release2, hold2+i);     // The maximum if we've just sold 2nd stock so far.
hold2    = Math.max(hold2,    release1-i);  // The maximum if we've just buy  2nd stock so far.
release1 = Math.max(release1, hold1+i);     // The maximum if we've just sold 1nd stock so far.
hold1    = Math.max(hold1,    -i);          // The maximum if we've just buy  1st stock so far.
}
return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1.
}
}``````
``````public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) return 0;
int kk = 2;
int len = prices.length;
int[][] dp = new int[kk + 1][len];
int res = 0;
for (int k = 1; k <= kk; k++) {
int tempMax = dp[k - 1][0] - prices[0];
for (int i = 1; i < len; i++) {
dp[k][i] = Math.max(dp[k][i - 1], prices[i] + tempMax);
tempMax = Math.max(tempMax, dp[k - 1][i] - prices[i]);
res = Math.max(res, dp[k][i]);
}
}
return res;
}
}``````