买卖股票的最佳两次交易

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

---

解法：

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

运行结果：

int[] prices = new int[]{6, 2, 1, 3, 5, 7, 6, 4, 8, 3, 5};

release2	hold2	release1	hold1
0	-6	0	-6
0	-2	0	-2
0	-1	0	-1
2	-1	2	-1
4	-1	4	-1
6	-1	6	-1
6	0	6	-1
6	2	6	-1
10	2	7	-1
10	4	7	-1
10	4	7	-1

int[] prices = new int[]{1, 3, 5, 2, 8, 10, 5, 3, 6, 7, 3};

release2	hold2	release1	hold1
0	-1	0	-1
2	-1	2	-1
4	-1	4	-1
4	2	4	-1
10	2	7	-1
12	2	9	-1
12	4	9	-1
12	6	9	-1
12	6	9	-1
13	6	9	-1
13	6	9	-1

hold1相当于找到最低值，release1是在hold1的基础上卖出能获得的最大收益。hold2相当于在release1的基础上买入的最大值，release2是在hold2的基础上卖出能获得的最大收益。