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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit(int[] prices) {
        // write code here
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        int[] dp1 = new int[len];
        int[] dp2 = new int[len];

        int profit = 0; // 利润
        int minPrices = prices[0]; // 最低的股票价格
        for (int i = 1; i < len; i++) {
            if (prices[i] - minPrices > profit) {
                profit = prices[i] - minPrices;
            }
            dp1[i] = profit;
            if (prices[i] < minPrices) {
                minPrices = prices[i];
            }
        }

        profit = 0; // 将利润重新置为 0
        int maxPrices = prices[len - 1]; // 最高的股票价格
        for (int j = len - 2; j > -1; j--) {
            if (maxPrices - prices[j] > profit) {
                profit = maxPrices - prices[j];
            }
            dp2[j] = profit;
            if (prices[j] > maxPrices) {
                maxPrices = prices[j];
            }
        }

        int finalProfit = 0;
        for (int i = 0; i < dp1.length; i++) {
            finalProfit = Math.max(dp1[i] + dp2[i], finalProfit);
        }
        return finalProfit;
    }
}