这道题要求的一个min和一个max，只是这个min所在的位置要在max所在位置的左边。

有一种做法是采用蛮力算法，也就是通过从左往右遍历，把每一个元素都当做min，然后再在这个元素的右边找一个最大值，这样得到一个profit，最后求得所有情况中profit的最大值即刻。但是这种做法的时间复杂度是O(n^2);

另一种做法是通过时间换空间的方法，我先用两个数组：数组1和数组2，数组1[i]表示从prices的第0个数到第i个数的最小值，数组2[i]表示从prices的第[len-1]个数到第i个数的最大值。

这种做法的时间复杂度是O(n),但是空间复杂度也是O(n).

所以如果有人想出时间复杂度是O(n)，且空间复杂度是O(1), 请告诉我下啊！！！

下面是另一种做法的AC代码：

1 /** 2      * Say you have an array for which the ith element is the price of a given stock on day i. 3      * If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),  4      * design an algorithm to find the maximum profit. 5      * @param prices 6      * @return 7      */ 8     public int maxProfit(int[] prices) { 9         if(prices==null || prices.length <= 1)10             return 0;11         int len = prices.length;12         //ma keep the minimum number till now.13         int[] ma = new int[len];14         //mia keep the maximum number from the end to now15         int[] mia = new int[len];16         ma[0] = prices[0];17         for(int i=1;i
     
      ma[i-1])19                 ma[i] = ma[i-1];20             else21                 ma[i] = prices[i];22         }23         mia[len-1] = prices[len-1];24         for(int i = len-2;i>=0;i--){25             if(prices[i]>mia[i+1])26                 mia[i] = prices[i];27             else28                 mia[i] = mia[i+1];29         }30         int max=0;31         for(int i=0;i
      
       max? mia[i]-ma[i]:max;33         }34         return max;35     }