LeetCode188—Best Time to Buy and Sell Stock IV

缺乏、安全感 2022-07-13 02:46 172阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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 k transactions.
> 
> Note:  
> You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

## 分析 ##

参考：[ LeetCode123—Best Time to Buy and Sell Stock III][LeetCode123_Best Time to Buy and Sell Stock III]  
将2次买卖扩展到k次。  
时间复杂度O(kn)空间复杂度可以O(n)也可以O(n2)

提交一直TLE，后来在discuss看到一种情况，也就是考虑当交易次数超过数组长度的一半时，可以用贪心来做，这样就可以降低时间复杂度了。参考：[https://discuss.leetcode.com/topic/12250/share-my-c-dp-solution-with-o-kn-time-o-k-space-10ms/12][https_discuss.leetcode.com_topic_12250_share-my-c-dp-solution-with-o-kn-time-o-k-space-10ms_12]

class Solution {
        public:
        int maxProfit(int k, vector<int>& prices) {
            if(prices.size()<=1)
                return 0;
            //vector< vector<int> > local(prices.size()+1,vector<int>(k+1));
            //vector< vector<int> > global(prices.size()+1,vector<int>(k+1));
    
            if (k>prices.size()/2){ // simple case
                int ans = 0;
                for (int i=1; i<prices.size(); ++i){
                    ans += max(prices[i] - prices[i-1],0);
                }
                return ans;
            }
    
            vector<int> local(k+1);
            vector<int> global(k+1);
            for(int i=0;i<prices.size()-1;++i)
            {
                int diff = prices[i+1]-prices[i];
                for(int j=k-1;j>=0;--j)
                {
                    local[j+1] = max(local[j+1]+diff, global[j]+max(0,diff) );
                    global[j+1]= max(global[j+1],local[j+1]);
                }
            }
            return global[k];
        }
    
    };

[Link 1]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
[LeetCode123_Best Time to Buy and Sell Stock III]: http://blog.csdn.net/zhangxiao93/article/details/51207636?locationNum=1&fps=1
[https_discuss.leetcode.com_topic_12250_share-my-c-dp-solution-with-o-kn-time-o-k-space-10ms_12]: https://discuss.leetcode.com/topic/12250/share-my-c-dp-solution-with-o-kn-time-o-k-space-10ms/12