Best Time to Buy and Sell Stock III

Say you have an array for which the ith 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).

解题思路：

题意为给定每天的股价，求最多两次交易最多的利润是多少？

我的想法是，最多一次交易的利润为P1（前面已经算出来了），最多两次的交易为P2，然后返回max(P1, P2)。

对于两次交易，可以看成两次一次交易。每次交易我们是在波峰/波谷中，因此，我们只需在每次的波峰/波谷中进行划分即可。

代码如下：

class Solution {
public:
    int maxProfit(vector& prices) {
        vector uniquePrices = uniqueNeighbor(prices);
        int len = uniquePrices.size();
        if(len == 0 || len == 1){
            return 0;
        }
        int oneProfit = maxProfitHelper(uniquePrices, 0, len-1); //一次交易
        //分成两次交易，每个波谷（或者波峰剪切）
        int twoProfit = 0;
        for(int i=1; i& prices, int start, int end){
        if(start>=end){
            return 0;
        }
        int result = 0;
        int minPrices = prices[start];
        for(int i=start+1; i<=end; i++){
            minPrices = min(prices[i], minPrices);
            result = max(result, prices[i] - minPrices);
        }
        return result;
    }
    vector uniqueNeighbor(vector& prices){
        vector result;
        int len = prices.size();
        if(len == 0){
            return result;
        }
        result.push_back(prices[0]);
        for(int i=1; i
注意这里首先将相邻价格的天合成一天（对结果没有影响），然后再计算，能够大大减少计算次数。但是最差的时间复杂度为O(n^2)，空间复杂度为O(1)。
另外一种方法是动态规划法。代码如下：
class Solution {
public:
    int maxProfit(vector& prices) {
        int len = prices.size();
        if(len<=1){
            return 0;
        }
        vector left(len, 0);
        vector right(len, 0);
        
        left[0] = 0;
        int minPrices = prices[0];
        for(int i=1; i=0; i--){
            maxPrices = max(prices[i], maxPrices);
            right[i] = max(right[i+1], maxPrices - prices[i]);
        }
        
        int maxProfit = 0;
        
        for(int i=0; i

 
转载请注明： » [LeetCode] Best Time to Buy and Sell Stock III

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->