题解 | #买卖股票的最好时机(三)#TOP82

思路:
1.两次交易，
2.记录一下第i天买入，到第n天之间卖出的最高价
3.再记录一下第0天到第i天之间最低价买入，第i天卖出的最高价
4.两次交易加起来取最大值。(同一天卖出、买入未尝不可)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length <= 1 ) {
            return 0;
        }
        int n = prices.length;
        //f[i] 代表第i天 买入 到第n天中间卖出的最高价
        //记录了从i点到之后的一次交易的最大收益
        //也就是卖出的最大收益
        int[] f = new int[n];
        //卖出的最高价
        int max = prices[n - 1];
        f[n - 1] = 0;
        for (int i = n - 2; i >= 0 ; i--) {
            //第i天到第n天卖出的最高价格
            max = Math.max(max, prices[i]);
            f[i] = Math.max(f[i + 1], max - prices[i]);
        }
        int result = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n ; i ++) {
            min = Math.min(min, prices[i]);
            result = Math.max(result, prices[i] - min + f[i] );
        }
        return result;

    }
}