Best Time to Buy and Sell Stock I, II, III(C++ code)

LeetCode Best Time to Buy and Sell StockOct 30 '12

 难度2， 出现频率1

Say you have an array for which the i^th 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.

0. int maxProfit(vector<int> &prices){  
1.   
2.    if(prices.empty()) return 0;  
3.   
4.    int profit = 0, minp = prices[0];  
5.   
6.    for(int i = 0; i < prices.size(); i++){  
7.   
8.       minp = min(minp, prices[i]);  
9.   
10.       profit = max(profit, prices[i] - minp);  
11.   
12.     }  
13.   
14.    return profit;  
15. }  

  
LeetCode Best Time to Buy and Sell Stock II,Oct 31
难度3 出现频率1 
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

0. int maxProfit(vector<int> &prices){  
1.   
2.    if(prices.empty()) return 0;  
3.   
4.    int profit = 0, start = 0, end = 0;  
5.   
6.    for(int i = 1; i < prices.size(); i++){  
7.   
8.       if(prices[i] >= prices[i-1]) end++;  
9.   
10.       else{  
11.   
12.         if(start < end) profit += prices[end] - prices[start];   
13.   
14.         start = end = i;  
15.       }      
16.     }  
17.   
18.    if(start < end) profit += prices[end] - prices[start];  
19.   
20.    return profit;  
21. }  

Best Time to Buy and Sell Stock III, Nov 7 '12
难度4，出现频率1
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路一(后面有最优解)： 对每一个点，计算左边一次交易右边一次交易得到的最大可能profit，每次新的计算update profit. 计算左边交易最大profit需要记录每个点的left minimum number，计算右边交易需要倒着记录每个点的right maximum number，并把右边profit结果存在一个数组里，以供循环从左到右使用。
时间复杂度O(n)，空间复杂度O(n).

int maxProfit(vector<int> &prices){
   if(prices.size() < 2) return 0;
   int n = prices.size();
   int proend = 0, profit;
   int rm = prices[n-1];
   int lm = prices[0];
   int prostart[n];
   prostart[n-1] = 0;
   for(int i = n-2; i >= 0 ; i--){
      rm = max(rm, prices[i]);     
      prostart[i] = max(prostart[i+1], rm - prices[i]);        
    }

   profit = prostart[0];

   for(int i = 1; i < n-1; i++){    
      lm = min(lm, prices[i]);
      proend = max(proend, prices[i] - lm);
      profit = max(profit, proend + prostart[i+1]);      
   }   
   
   return profit;
      
}

思路二： 来源： http://www.mitbbs.com/article/JobHunting/32289973_0.html
这是最优解，时间O(n),空间O（1）
其实我开始也想用DP做，想了下以为不行，结果还是我思考的不够仔细，恩，虽然解法原帖已经贴了，我还是自己练一个。
主要思路分下如下：
要找当前点i进行两个交易的最大收益，两种可能：
1，不包括当前点i：结果是在前一点i-1进行两个交易的最大收益，这是第一层DP
2， 包括当前点i： 起始点可能是任何j<i, 结果是在j-1点进行一次交易+buy j sell i交易的最大可能收益。这里比较tricky,实际上我们可以通过定义另外一个DP来省去重复计算，关键的观察是：
prices[i]- prices[j] = prices[i] - prices[i-1] + prices[i-1] - prices[j] 
所以这里我们可以设定第二层DP

结论： g(m)-> 到当前点为止最多进行m次交易最大可能收益
           f(m)-> 到当前点为止最多m次交易，并包括当前点的最大可能收益，注意最后一次交易可能只包括i-1,i这两点，这种情况下f_i(m) = price[i] - price[i-1] + g_i-1(m-1).

所以在点i:
         f_i(m) =   price[i] - prices[i-1] + max(f_i-1(m), g_i-1(m-1))
         g_i(m) = max(f_i(m),g_i-1(m))

代码如下（比原帖优化了一点）：

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