/*
 * @lc app=leetcode id=123 lang=java
 *
 * [123] Best Time to Buy and Sell Stock III
 */

// @lc code=start
class Solution {
    public int maxProfit(int[] prices) {
        int[] ldp = new int[prices.length];
        int[] rdp = new int[prices.length];
        for(int i=0; i<ldp.length; i++) {
            ldp[i] = 0;
            rdp[i] = 0;
        }
        int lmin = prices[0], maxProfit=0;
        for(int i=1; i<ldp.length; i++) {
            maxProfit = Math.max(maxProfit, prices[i]-lmin);
            lmin = Math.min(lmin, prices[i]);
            ldp[i] = maxProfit;
        }
        int rmax = prices[prices.length-1];
        maxProfit = 0;
        for(int i=rdp.length-2; i>=0; i--) {
            maxProfit = Math.max(maxProfit, rmax - prices[i]);
            rmax = Math.max(rmax, prices[i]);
            rdp[i] = maxProfit;
        }
        int profit = ldp[ldp.length-1];
        for(int i=0; i<ldp.length-1; i++) {
            profit = Math.max(profit, ldp[i] + rdp[i+1]);
        }
        return profit;
    }
}
// @lc code=end