Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
一刷
题解：
dp的原理，但是数组长度为常数。
hold[2], sold[2]分别表示:hold[0], hold[1]表示第一次买入， 第二次买入的最小代价，sold[0], sold[1]表示第一，第二次卖出后的最大利润。
注意，更新顺序为sold[0], hold[0], sold[1], hold[1]， 因为hold[I]需要根据sold[I]的信息。
public class Solution {
public int maxProfit(int[] prices) {
int[] hold = new int[2];
int[] sold = new int[2];
Arrays.fill(hold, Integer.MIN_VALUE);
for(int price : prices){
sold[0] = Math.max(price + hold[0], sold[0]);
hold[0] = Math.max(hold[0], -price);//hold the minimum number
sold[1] = Math.max(sold[1], price + hold[1]);
hold[1] = Math.max(hold[1], sold[0] - price);
}
return sold[1];
}
}
