[LeetCode] 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.

思路1：第i天买入，能赚到的最大利润是多少呢？就是i + 1 ~ n天中最大的股价减去第i天的。

思路2：第i天买出，能赚到的最大利润是多少呢？就是第i天的价格减去 0~ i-1天中最小的。

我这里只对思路一做了实现，思路2对于Best Time to Buy and Sell StockIII很有用。。。

方法一：

step1，用动态规划思想，找到i ~ n天中的最大值，保存到maxPrice Array中。

step2，计算prices[i] - maxPrice[i+1]的最大值

时间复杂度O（n），空间复杂度O（n）

 1 class Solution {
 2     public:
 3         int maxProfit(vector<int> &prices) 
 4         {   
 5             vector<int> maxPrice;
 6             maxPrice.resize(prices.size(), 0); 
 7             int res = 0;
 8             
 9             if(prices.size() == 0)
10                 return res;
11 
12             maxPrice[prices.size() -1] = prices[prices.size() -1];
13             for(int i = prices.size() -2; i>= 0; i--)
14             {   
15                 if(prices[i] > maxPrice[i+1])
16                     maxPrice[i] = prices[i];
17                 else
18                     maxPrice[i] = maxPrice[i+1];
19             }   
20 
21             //printVector(maxPrice );
22 
23             for(int i = 0; i < prices.size() -1; i++)
24             {   
25                 res = max(res,  maxPrice[i+1] - prices[i]);
26             }   
27             return res;
28         }   
29 };

方法二：

时间复杂度O（n），空间复杂度O（1）的方法，计算最大利润和计算最大值同步进行。。

用maxPrice[i]记录从 price[i+1] 到price[n-1]的最大值，这样可以一次扫描就可以算出最大利润和price的最大值，空间复杂度O（1）

 1 class Solution {
 2     public:
 3         int maxProfit(vector<int> &prices)
 4         {
 5             int res = 0;
 6 
 7             if(prices.size() == 0)
 8                 return res;
 9 
10             int maxPrice = prices[prices.size() -1];
11 
12             for(int i = prices.size() - 2; i>=0; i--)
13             {
14                 res =  max(res, maxPrice - prices[i]);
15                 maxPrice = max(maxPrice, prices[i]);
16             }
17             return res;
18         } 
19 };