[leetcode]Best Time to Buy and Sell Stock I II III - java O(n)

问题1比较简单， 使用一个pre变量，记录之前最小值就可以了

public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = 0;
        int minPre = prices[0];
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            if(price<minPre){
                minPre = price;
            }else if(price-minPre>max){
                max = price-minPre;
            }
        }
        return max;
    }

 问题2细想，其实也比较简单，就是将所有递增的两个数的差加起来

public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int preMin = prices[0];
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            if (price < preMin) {
                preMin = price;
            } else if (price > preMin) {
                sum += price - preMin;
            }
            preMin = prices[i];
        }
        return sum;
    }

 第三个问题，需要细想下，直观的想法，将数组一份为二，得到没有个子数组的最大值，这个算法是O(n2)的时间复杂度，不过；仔细思考，其实我们可以通过三次o(n)的遍历，得到所求。事先我们可以得到正向遍历，反向遍历，每个index上的最大利润值，最后一次遍历就可完成计算。

 

 public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int[] maxLeft = new int[prices.length];
        int preMin = prices[0];
        for(int i=1; i<prices.length; i++){
            int price = prices[i];
            if(price<preMin){
                preMin=price;
                maxLeft[i] =maxLeft[i-1];
            }else if(price-preMin>maxLeft[i-1]) {
                maxLeft[i]=price - preMin;
            }else {
                maxLeft[i] =maxLeft[i-1];
            }
        }
        int[] maxRight = new int[prices.length];
        int preMax = prices[prices.length-1];
        for(int i=prices.length-2; i>=0; i--){
            int price = prices[i];
            if(price>preMax){
                preMax = price;
                maxRight[i] = maxRight[i+1];
            }else  if(preMax - price>maxRight[i+1]){
                maxRight[i]=preMax - price;
            }else {
                maxRight[i] = maxRight[i+1];
            }
        }
        int max =0;
        for(int i=1; i<prices.length; i++){
           if(maxLeft[i]+maxRight[i]>max){
               max = maxLeft[i]+maxRight[i];
           }
        }
        return max;
    }