package question0123_best_time_to_buy_and_sell_stock_iii;

/**
 * 做两次question0121。
 *
 * 时间复杂度是O(n ^ 2)，其中n为prices数组的长度。空间复杂度是O(1)。
 *
 * 执行用时：870ms，击败5.01%。消耗内存：39.7MB，击败30.34%。
 */
public class Solution1 {
    public int maxProfit(int[] prices) {
        int result = 0, n = prices.length;
        if (n == 0) {
            return result;
        }
        for (int i = 1; i < n; i++) {
            //第一笔交易在[0, i]天内完成，第二笔交易在[i + 1, n - 1]天内完成
            result = Math.max(maxProfit(prices, 0, i) + maxProfit(prices, i + 1, n - 1), result);
        }
        return result;
    }

    private int maxProfit(int[] prices, int left, int right) {
        int result = 0;
        if (right - left < 1) {
            return result;
        }
        int minPrice = prices[left];
        for (int i = left + 1; i <= right; i++) {
            result = Math.max(result, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return result;
    }
}