package leetcode.oj.bestTimeSellAndBuyTheStock;

//http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/

public class Solution {

	public int maxProfit(int[] prices) {
		if (prices.length < 2) {
			return 0;
		}
		return find(prices, prices.length - 1);
	}

	public int find(int[] arr, int maxIdx) {
		if (maxIdx < 1) {
			return 0;
		}
		int min = arr[0];
		int minIdx = 0;
		for (int i = 1; i <= maxIdx; i++) {
			if (arr[i] < min) {
				min = arr[i];
				minIdx = i;
			}
		}

		// Find right max
		int maxRight = 0;
		for (int i = minIdx + 1; i <= maxIdx; i++) {
			int tmp = arr[i] - min;
			if (tmp > maxRight) {
				maxRight = tmp;
			}
		}
		int maxLeft = 0;
		if (minIdx == 2) {
			maxLeft = arr[1] - arr[0];
		} else if (minIdx > 2) {
			maxLeft = find(arr, minIdx - 1);
		}

		if (maxRight > maxLeft) {
			return maxRight;
		} else {
			return maxLeft;
		}
	}
}

@@ -170,25 +170,28 @@
  prices) %7B%0A%09
-%09
+    
 if (prices.l
@@ -197,25 +197,21 @@
 length %3C
- 2) %7B%0A%09%09%09
+= 1) 
 return 0
@@ -216,177 +216,61 @@
  0;%0A
-%09%09%7D%0A%09%09return find(prices, prices.length - 1);%0A%09%7D%0A%0A%09public int find(int%5B%5D arr, int maxIdx) %7B%0A%09%09if (maxIdx %3C 1) %7B%0A%09%09%09return 0;%0A%09%09%7D%0A%09%09int min = arr%5B0%5D;%0A%09%09int minIdx = 0;%0A%09%09
+%0A%09    int profit = 0;%0A%09    int min = prices%5B0%5D;%0A%09    
 for 
@@ -282,487 +282,160 @@
 i = 
-1
+0
 ; i %3C
-= maxIdx; i++) %7B%0A%09%09%09if (arr%5Bi%5D %3C min) %7B%0A%09%09%09%09min = arr%5Bi%5D;%0A%09%09%09%09minIdx = i;%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09// Find right max%0A%09%09int maxRight = 0;%0A%09%09for (int i = minIdx + 1; i %3C= maxIdx; i++) %7B%0A%09%09%09int tmp = arr%5Bi%5D - min;%0A%09%09%09if (tmp %3E maxRight) %7B%0A%09%09%09%09maxRight = tmp;%0A%09%09%09%7D%0A%09%09%7D%0A%09%09int maxLeft = 0;%0A%09%09if (minIdx == 2) %7B%0A%09%09%09maxLeft = arr%5B1%5D - arr%5B0%5D;%0A%09%09%7D else if (minIdx %3E 2) %7B%0A%09%09%09maxLeft = find(arr, minIdx - 1);%0A%09%09%7D%0A%0A%09%09if (maxRight %3E maxLeft) %7B%0A%09%09%09return maxRight;%0A%09%09%7D else %7B%0A%09%09%09return maxLef
+ prices.length; i++) %7B%0A%09        min = Math.min(min, prices%5Bi%5D);%0A%09        profit = Math.max(profit, prices%5Bi%5D - min);%0A%09    %7D%0A%09    return profi
 t;%0A
-%09
 %09%7D%0A
-%09%7D
 %0A%7D%0A

change the solution