一、题目 Say you have an array for which the ith 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.
Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0
In this case, no transaction is done, i.e. max profit = 0. 二、分析和解答 股票只能今天买，今天之后的某一天卖！也就是求某两天价格最大的差距，且低价买入高价卖出！ 1、先来个时间复杂度高的，没有AC，超时
public int maxProfit(int[] prices) { int max = 0; for(int i=0;i<prices.length-1;i++){ for(int j=i+1;j<prices.length;j++){ int value = prices[j] - prices[i]; if(value >= 0 && max < value) max = value; } } return max; }2、优化 记录到第i天之前的最小的价格minPrice（即到目前为止的最低价格），再计算当前的价格与最小价格的差值，这个就是利润，如果比之前的大，那就更新最大利润！
public int maxProfit(int[] prices) { if(prices.length == 0) return 0; int minPrice = prices[0]; int profit = 0; for(int i=1;i<prices.length;i++){ //找到更低的买入价 if(minPrice > prices[i]){ minPrice = prices[i]; } //当前的利润 int diff = prices[i] - minPrice; if(profit < diff) profit = diff;//更新最大利润 } return profit; }注意：当输入数组长度为0，返回0。 据说这个是动态规划，它记录了到目前为止最小的值。
我想到的是通过最大和最小的差值和第一个数进行比较，这是不对的，万一有个[7,2,6,1]的顺序，是计算不出来2这个数的！应该想到最小值的！
如何描述O(n^2)的算法过渡到O(n)的算法呢？会描述了，懂得了优化的原因才可以！
后来我想通过第一个数先找到最小的一个数，然后再找最小的数后面的一个最大的数，再进行减法。这样是不对的，（哪怕保证最后一位不是最小值）因为最小值参与的计算也不一定最大的，比如：[5,2,6,4,0,3]，只要两个数的差值最大即可。所以不能找全局最小的值，而是找到目前为止的最小的值，将其记录下来！
