Best Time to Buy and Sell Stock

Q:
Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

A:
 ------------------3 rd pass -----------------
--就是很简单的一遍过即可---------不知道为什么，当时非要那么麻烦-----------------------------------------

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int minBefore = Integer.MAX_VALUE;
        int result = 0;
        for(int i = 1;i<n;i++){
            minBefore = Math.min(minBefore,prices[i-1]);
            result = Math.max(result,  prices[i] - minBefore );
        }
        return result;
    }
}

就是CLRS上的，divide and conquer 问题。
第一遍做的，有点儿问题。（ 虽然也pass了）
例如： 上来直接设  leftMax =0  是不对的。  有可能很小。  因为，对于cross的， 就是假定了， 左右，都必须含有。因此，需要先设为： 负无穷 （ CLRS上也是这样的）

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices!= null && prices.length<=1){
            return 0;
        }
        int[] change = new int[prices.length];
        for(int i =0; i<prices.length-1;i++){
            change[i] = prices[i+1] - prices[i];
        }
        return maxChange(change, 0 ,change.length-1);
    }
    //divide and conquere problem.
    public int maxChange(int[] change, int start, int end){
        if(start==end){
            return change[start];
        }
        else{
            int middle = (int)((start+end)/2);
            int leftMax = maxChange(change, start,middle);
            int rightMax = maxChange(change, middle+1, end);
            int crossMax = maxCross(change,start,middle,end);
            int maxProfit = (leftMax>rightMax)?leftMax:rightMax;
            if(crossMax > maxProfit){
                maxProfit = crossMax;
            }
            return maxProfit;
        }
        
    }
    private int maxCross(int[] change, int start, int middle, int end){
        //get max left part
        int leftMax = 0;
        int sum=0;
        for(int i =middle; i>=start; i--){
            sum += change[i];
            if(sum>leftMax){
                leftMax = sum;
            }
        }
        int rightMax = 0;
        sum = 0;
        for(int i =middle+1; i<=end; i++){
            sum +=change[i];
            if(sum>rightMax){
                rightMax=sum;
            }
        }
        return leftMax + rightMax;
    }
}