代码随想录Day50——123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

123.买卖股票的最佳时机III?

给定一个数组，它的第?i?个元素是一支给定的股票在第?i?天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成?两笔?交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

//超时
/*class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1) return 0;
        if(prices.size() == 2) return prices[0]<prices[1]?prices[1]-prices[0]:0;
        int result = 0,min1 = prices[0],min2 = prices[2],result1 = 0,result2 = 0;
        for(int i = 1;i<prices.size();i++)
        {
            min2 = i<prices.size()-1?prices[i+1]:0;
            result2 = 0;
            for(int j = i-1;j<=i;j++)
            {
                if(prices[j]<min1) min1 = prices[j];
                result1 = max(result1,prices[j] - min1);
            }
            for(int j = i+1;j<prices.size();j++)
            {
                if(prices[j]<min2) min2 = prices[j];
                result2 = max(result2,prices[j] - min2);
            }
            result = max(result,result1+result2);
        } 
        return result;
    }
};*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.size() - 1][4];
    }
};

188.买卖股票的最佳时机IV?

给你一个整数数组?prices?和一个整数?k?，其中?prices[i]?是某支给定的股票在第?i?天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成?k?笔交易。也就是说，你最多可以买?k?次，卖?k?次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int l = prices.size();
        vector<int> v(2*k+1,0);
        vector<vector<int>> dp(l,v);
        for(int j = 1;j<=2*k;j++)
        {
            if(j%2 == 1) dp[0][j] = -prices[0];
        }
        for(int i = 1;i<prices.size();i++)
        {
            for(int j = 0;j<=2*k;j++)
            {
                if(j == 0)
                {
                    dp[i][j] = dp[i-1][0];
                }
                else if(j%2 == 1)
                {
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i]);
                }
                else if(j%2 == 0)
                {
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] + prices[i]);
                }
            }
        }
        return dp[l-1][2*k];
    }
};