Best Time to Buy and Sell Stock III
Question
Array for ith price for day i. Find the maximum profit within two transactions. Stock must be sold before buying again.
Analysis
Typical DP question. Using 4 vaiables to represent the revenue after selling 1st and 2nd stock and the hold on value after buying 1st and 2nd stock.
Revenue1 = max(revenue1, hold1 + boughtPrice)
Hold1 = max(hold1, -boughtPrice)
Revenue2 = max(revenue2, hold2 + boughtPrice)
Hold2 = max(revenue1 - boughtPrice, hold2)
Code
public class Solution {
public int maxProfit(int[] prices) {
// dp - buy OR not
// the largest revnue happens when we sold all the stock
// so we have revenue1, revenue2, hold1, hold2
int revenue1 = 0, revenue2 = 0;
int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
for(int p: prices){
revenue1 = Math.max(revenue1, hold1+p); // after we sold 1st stock
hold1 = Math.max(-p, hold1); // after we bought 1st stock
revenue2 = Math.max(revenue2, hold2+p); // after we sold 2nd stock
hold2 = Math.max(revenue1-p, hold2); // after we bought 2nd stock
} // for p
return Math.max(revenue1, revenue2);
}
}
做过了好几个买股票的题依旧买不好股票呢(笑)。。。