123. Best Time to Buy and Sell Stock III

Problem:

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.

Analysis:

太难了，分析不出来。

Solution:

为什么要反着写？
因为卖依赖的是之前的买，第二次依赖的是之前的第一次。

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
        int sell1 = 0, sell2 = 0;
        for (int price: prices) {
            sell2 = Math.max(sell2, buy2 + price);
            buy2 = Math.max(buy2, sell1 - price);
            sell1 = Math.max(sell1, buy1 + price);
            // buy1是负数， max 就是找花钱最少的
            buy1 = Math.max(buy1, -price);
        }
        return sell2;
    }
}