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