Best Time to Buy and Sell Stock 3

题目地址：

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/#/description

题目：

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

解题思路：这道题需要维持两个array来存两个方向的最大利润。总体思路是动态规划。

代码：

public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1){
        return 0;
    }
    int len = prices.length;
    int[] premax = new int[len];
    int[] postmax = new int[len];
    int min = prices[0];
    for(int i = 1; i <= len - 1; i++){
        min = Math.min(min, prices[i]);
        premax[i] = Math.max(premax[i - 1], prices[i] - min);
    }
    int max = prices[len - 1];
    for(int i = len - 2; i >= 0; i--){
        max = Math.max(max, prices[i]);
        postmax[i] = Math.max(postmax[i + 1], max - prices[i]);
    }
    int rst = 0;
    for(int i = 0; i <= len - 1; i++){
        rst = Math.max(rst, premax[i] + postmax[i]);
    }
    return rst;
}