【每日刷题】Day118

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 123. 买卖股票的最佳时机 III - 力扣（LeetCode）

2. 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

3. 53. 最大子数组和 - 力扣（LeetCode）

1. 123. 买卖股票的最佳时机 III - 力扣（LeetCode）

//思路：多动态dp问题。

//本题的思路与 "买卖股票的最佳时机Ⅱ" 较为类似，具体细节变化看图解：

class Solution {

public:

    const int INF = 0x3f3f3f3f;

    int maxProfit(vector<int>& prices)

    {

        int n = prices.size(),ans = 0;

        vector<vector<int>> f(n,vector<int>(3,-INF));

        auto g = f;

//初始化第一天的情况

        f[0][0] = -prices[0];

        g[0][0] = 0;

        for(int i = 1;i<n;i++)

        {

            for(int j = 0;j<3;j++)

            {

                f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);

                g[i][j] = g[i-1][j];

                if(j-1>=0) g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);

            }

        }

        for(int j = 0;j<3;j++) ans = ans>g[n-1][j]?ans:g[n-1][j];

        return ans;

    }

};

2. 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

//思路：多状态do问题

//思路与上一题 "买卖股票的最佳时机Ⅲ" 完全一样，只不过将交易次数从 2 改为了 k，代码也只需要改变循环的次数即可。

class Solution {

public:

    const int INF = 0x3f3f3f3f;

    int maxProfit(int k, vector<int>& prices)

    {

        int n = prices.size(),ans = 0;

        vector<vector<int>> f(n,vector<int>(k+1,-INF));

        auto g = f;

        f[0][0] = -prices[0];

        g[0][0] = 0;

        for(int i = 1;i<n;i++)

        {

            for(int j = 0;j<k+1;j++)

            {

                f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);

                g[i][j] = g[i-1][j];

                if(j-1>=0) g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);

            }

        }

        for(int j = 0;j<k+1;j++) ans = ans>g[n-1][j]?ans:g[n-1][j];

        return ans;

    }

};

3. 53. 最大子数组和 - 力扣（LeetCode）

//思路：动态规划子数组问题。

class Solution {

public:

    const int INF = 0x3f3f3f3f;

    int maxSubArray(vector<int>& nums)

    {

        int n = nums.size(),ans = -INF;

        vector<int> dp(n);

        dp[0] = nums[0];

        for(int i = 1;i<n;i++) dp[i] = max(nums[i],nums[i]+dp[i-1]);

        for(int i = 0;i<n;i++) ans = ans>dp[i]?ans:dp[i];//最后遍历寻找记录的最大和

        return ans;

    }

};