# Untitled

a guest
Aug 17th, 2019
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2.     public int maxProfit(int[] prices) {
3.         return solve(prices, 1);
4.     }
5.     int solve(int[] prices, int pass) {
6.                 int n = prices.length;
7.         int min = Integer.MAX_VALUE, maxProfit = 0;
8.         int i = -1, buyIndex = -1, sellIndex = -1;
9.         for (int x = 0; x < n; x++) {
10.             if (min > prices[x]) {
11.                 min = prices[x];
12.                 i = x;
13.             } else if (maxProfit < prices[x] - min) {
14.                 maxProfit = prices[x] - min;
15.                 sellIndex = x;
16.                 buyIndex = i;
17.             }
18.         }
19.         if (maxProfit == 0) return 0;
20.         return maxProfit + pass == 2? 0 : Math.max(solve(Arrays.copyOfRange(prices, 0, buyIndex - 1), 2), solve(Arrays.copyOfRange(prices, sellIndex+1, n-1), 2));
21.     }
22. }
RAW Paste Data