美文网首页
Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

作者: lmem | 来源:发表于2016-12-20 21:48 被阅读8次

    虽然解出来了,但是不是最优的方法

    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).
    
    [Subscribe](https://leetcode.com/subscribe/) to see which 
    companies asked this question
    
    Show Tags
    
    Show Similar Problems
    
    class Solution(object):
        """
        :type prices: List[int]
        :rtype: int
        """
        def maxProfit(self, prices):
            if len(prices) == 0 or len(prices) == 1:
                return 0
            F =[0] #当前效益最大值
            min=prices[0] #最小值
            Max = 0
            n=len(prices)
            for i in range(n-1):
                F.append(F[i] if F[i] > prices[i+1]-min else prices[i+1]-min)
                min = min if prices[i+1] > min else prices[i+1]
            T = [0]
            max=prices[n-1] #最大值
            for i in range(1,n):
                T.append(T[i-1] if T[i-1] > max-prices[n-i-1] else  max-prices[n-i-1] )
                max = max if prices[n-i-1] < max else prices[n-i-1]
            for i in range(0,n):
                Max = Max if Max > T[n-1-i]+F[i] else T[n-1-i]+F[i]
            return Max
    

    看下面的解法

    #前i次 交易j次的利润
    f[j][i] = max(f[j][i-1], prices[i] +maxtmp);
    #最大临时值
    maxtmp=max(maxtmp,f[i][j - 1] - price[i]);
    
    class Solution {  
    public:  
        int maxProfit(vector<int>& prices) {  
            if (prices.size() < 2)   
                return 0;  
            vector< vector<int> > f(3, vector<int>(prices.size(), 0));  
            for (int j = 1; j <= 2; j++) {  
                int tmpMax = f[j-1][0] - prices[0];  
                for (int i = 1; i < prices.size(); i++) {  
                    f[j][i] = max(f[j][i-1], prices[i] + tmpMax);  
                    tmpMax = max(tmpMax, f[j-1][i] - prices[i]);  
                }  
            }  
            return f[2][prices.size()-1];  
        }  
    };  
    

    相关文章

      网友评论

          本文标题: Best Time to Buy and Sell Stock

          本文链接:https://www.haomeiwen.com/subject/ndjfvttx.html