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

import java.util.*;


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