首页 > 代码库 > Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock
https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/
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.
解题思路：
只允许买卖一次。假定考虑第一个数字作为买入值，往后找卖出值。只要该值大于买入值，就用这个值减去买入值，作为利润存入变量，不断比较算出最高利润。但只要遇到一个比买入值还要低的数字，就意味着买入值要替换为该数字，如此往复。
原因是，想象一个涨涨跌跌的曲线，这里需要对比的并不是曲线的涨跌（前后两天数字的大小），即便曲线跌了，但只要不跌过第一个值（买入值），不要卖，后面仍有可能涨上去。但此时前面也肯定有一个最大利润额。只要一旦跌过第一个值了，就说明前面要卖了。所以更新买入值到此处，同时更新前面的最大利润额。关键在于对比的是当前值和第一天值的大小，而不是当前值和前一天的值大小。
其实，这就是一个动态规划算法。
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; for(int i = 0; i < prices.length;){ int j = i + 1; while(j < prices.length && prices[j] >= prices[i]){ j ++; maxProfit = maxProfit > prices[j - 1] - prices[i] ? maxProfit :prices[j - 1] - prices[i]; } i = j; } return maxProfit; }}
这是一个对上面算法的直接实现。两层循环，算法复杂度O(n^2)，但是外层循环，i并非以1递增，而是直接跳到j，（根据上面的描述，直接增加到跌过买入值的那天）。所以事实时间复杂度接近O(n)。
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; int min = 0; if(prices.length == 0){ return 0; }else { min = prices[0]; } for(int i = 0; i < prices.length; i++){ if(prices[i] < min){ min = prices[i]; } maxProfit = maxProfit > prices[i] - min ? maxProfit :prices[i] - min; } return maxProfit; }}
这是一个O(n)的实现。考虑到上面要记录的并非是i的值，而仅仅是prices[i]，可以将其存入变量中，这样仅用一个i就能实现了。但是似乎没有第一个代码易于理解。
Best Time to Buy and Sell Stock