[Leetcode] Best Time to Buy and Sell Stock III

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         int n=prices.length;
 4         if (n <= 1)
 5             return 0;
 6         int[] l2r = new int[n];
 7         int[] r2l = new int[n];
 8         l2r[0] = 0;
 9         r2l[n-1] = 0;
10         int minn = prices[0];
11         for (int i = 1; i < n; i++) {
12             minn = Math.min(minn, prices[i]);
13             l2r[i] = Math.max(l2r[i - 1], prices[i] - minn);
14         }
15         int maxx = prices[n - 1];
16         for(int i=n-2;i>=0;i--){
17             maxx=Math.max(maxx, prices[i]);
18             r2l[i]=Math.max(r2l[i+1], maxx-prices[i]);
19         }
20         int result=l2r[n-1];
21         for(int i=0;i<n-1;i++){
22             result=Math.max(result, l2r[i]+r2l[i+1]);
23         }
24         return result;
25     }
26 }