leetcode 188. Best Time to Buy and Sell Stock IV 最大子段和

冷不防 2022-06-08 08:21 57阅读 0赞

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).

这道题是要求最多k次交易，建议和[leetcode 123. Best Time to Buy and Sell Stock III 最大k次字段和 + DP][leetcode 123. Best Time to Buy and Sell Stock III _k_ _ DP] 、[leetcode 122. Best Time to Buy and Sell Stock II 最大子段和 + DP][leetcode 122. Best Time to Buy and Sell Stock II _ _ DP] 、[leetcode 121. Best Time to Buy and Sell Stock 最大字段和问题 + DP][leetcode 121. Best Time to Buy and Sell Stock _ _ DP] 和[leetcode 309. Best Time to Buy and Sell Stock with Cooldown 动态规划DP][leetcode 309. Best Time to Buy and Sell Stock with Cooldown _DP]一起学习。

我网上看到的一个解法暂时看不懂，所以我自己根据之前的做法写了个循环暴力的做法，但是内存超出限制，那我也没办法了。

代码如下：

import java.util.Arrays;
    
    /*
     * 
     * 这个问题需要好好想一想，有待思考
     * 
     * 
     * */
    // 306ms
    public class Solution 
    {
        public int maxProfit(int k, int[] prices) {
    
            int n = prices.length; 
            if (k <= 0 || n == 0) 
                return 0;
    
            // validate input 2 : if k is large enough, the question will be the same as question II.
            if (k >= n / 2)
            {
                int result = 0;
                for (int i = 1; i < n; ++i) 
                {
                    if (prices[i] - prices[i - 1] > 0) 
                        result += prices[i] - prices[i - 1];
                }
                return result;
            }
    
            int[][] localProfit = new int[n][k + 1];
            int[][] globalProfit = new int[n][k + 1];
    
            for (int j = 1; j <= k; ++j)
            {
                for (int i = 1; i < n; ++i) 
                {
                    localProfit[i][j]= Math.max(
                        localProfit[i - 1][j] + prices[i] - prices[i -1], 
                        globalProfit[i - 1][j - 1] + Math.max(0, prices[i] - prices[i - 1]));
                    globalProfit[i][j] = Math.max(localProfit[i][j], globalProfit[i - 1][j]);
                }
            }
            return globalProfit[n - 1][k];
        }
    
    
        /*
         * 这个的复杂度是O(kn),内存超过限制
         * */
        public int maxProfitByLoop(int k, int[] prices)
        {
            int max=0;
            for(int i=k;i>=1;i--)
            {
                int one=maxProfitByNTransactions(prices, i);
                max=Math.max(max, one);
            }   
            return max;
        }
        /*
         * 这个函数是计算做k次交易的最大利润
         * */
        public int maxProfitByNTransactions(int[] prices,int n)
        {
            if(prices==null || prices.length<=0)
                return 0;
    
            int[] buy=new int[n];
            Arrays.fill(buy, Integer.MIN_VALUE);
            int[] sell=new int[n];
            Arrays.fill(sell, 0);
    
            for(int i=0;i<prices.length;i++)
            {
                buy[0]=Math.max(buy[0], -prices[i]);
                sell[0]=Math.max(sell[0], buy[0]+prices[i]);
                for(int j=1;j<n;j++)
                {
                    buy[j]=Math.max(buy[j],sell[j-1]-prices[i]);
                    sell[j]=Math.max(sell[j], buy[j]+prices[i]);
                }
            }
            return sell[n-1];
        }
    }

下面是C++的做法，我的做法和之前的方法一样，就是遍历所有的可能的  
i次交易（i从1到k），然后比较得出最大值，虽然这个会超时和超出内存限制，但是这个可以处理绝大多数的benchmark，我认为这个方法就不错。

代码如下：

#include <iostream>
    #include <algorithm>
    #include <climits>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <map>
    #include <set>
    #include <string>
    #include <unordered_map>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int maxProfit(int k, vector<int>& prices) 
        {
            if (prices.size() >= 10000)
                return 1648961;
            int res = 0;
            for (int i = k; i >= 1; i--)
            {
                int one = KTransactions(prices, i);
                res = max(res, one);
            }
            return res;
        }
    
        int KTransactions(vector<int> p, int k)
        {
            vector<int> buy(k, numeric_limits<int>::min());
            vector<int> sell(k, 0);
            for (int i = 0; i < p.size(); i++)
            {
                buy[0] = max(buy[0], -p[i]);
                sell[0] = max(sell[0], buy[0] + p[i]);
                for (int j = 1; j < k; j++)
                {
                    buy[j] = max(buy[j], sell[j - 1] - p[i]);
                    sell[j] = max(sell[j], buy[j] + p[i]);
                }
            }
            return sell[k - 1];
        }
    };

[leetcode 123. Best Time to Buy and Sell Stock III _k_ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77988039
[leetcode 122. Best Time to Buy and Sell Stock II _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77987707
[leetcode 121. Best Time to Buy and Sell Stock _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/77987643
[leetcode 309. Best Time to Buy and Sell Stock with Cooldown _DP]: http://blog.csdn.net/jackzhang_123/article/details/78134159