public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        /*
         * DP from left to right. Recurrence:
         * leftMaxProfit[i] = Math.max(leftMaxProfit[i-1], prices[i] - minBuyingPrice)
         */
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            minPrice = Math.min(minPrice, prices[i]);
            left[i] = Math.max(left[i - 1], prices[i] - minPrice);
        }
        /*
         * DP from right to left. Recurrence:
         * rightMaxProfit[i] = Math.max(rightMaxProfit[i+1], maxSellingPrice - prices[i])
         */
        int maxPrice = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; --i) {
            maxPrice = Math.max(maxPrice, prices[i]);
            right[i] = Math.max(right[i + 1], maxPrice - prices[i]);
        }
        int maxProfit = 0;
        for (int i = 0; i < prices.length; ++i) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        return maxProfit;
    }