class Solution {
    public int maxProfit(int[] prices) {
        return solve(prices, 1);
    }
    int solve(int[] prices, int pass) {
                int n = prices.length;
        int min = Integer.MAX_VALUE, maxProfit = 0;
        int i = -1, buyIndex = -1, sellIndex = -1;
        for (int x = 0; x < n; x++) {
            if (min > prices[x]) {
                min = prices[x];
                i = x;
            } else if (maxProfit < prices[x] - min) {
                maxProfit = prices[x] - min;
                sellIndex = x;
                buyIndex = i;
            }
        }
        if (maxProfit == 0) return 0;
        return maxProfit + pass == 2? 0 : Math.max(solve(Arrays.copyOfRange(prices, 0, buyIndex - 1), 2), solve(Arrays.copyOfRange(prices, sellIndex+1, n-1), 2));
    }
}