【算法挨揍日记】day25——123. 买卖股票的最佳时机 III、188. 买卖股票的最佳时机 IV

心已赠人 2024-02-19 08:46 10阅读 0赞

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

[123. 买卖股票的最佳时机 III][123. _ III]

### 题目描述： ###

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

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

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

![2b8741e31d7a4defad31519be575613c.png][]

### 解题思路： ###

> 状态表示：
> 
> f\[i\]\[j\]表示第i天结束后，完成了j次交易后处于买入状态下的最大利润
> 
> f\[i\]\[j\]表示第i天结束后，完成了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\]);
> 
> 初始化：
> 
> f和g的第一行都为-0x3f3f3f
> 
> f\[0\]\[0\]=-prices\[0\];
> 
> g\[0\]\[0\]=0;
> 
> 填表顺序;左到右，上到下
> 
> 返回值，最后一行的最大值  
>

### 解题代码： ###

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int n=prices.size();
            vector<vector<int>>f(n,vector<int>(3,-0x3f3f3f));
            vector<vector<int>>g(n,vector<int>(3,-0x3f3f3f));
            f[0][0]=-prices[0];
            g[0][0]=0;
            int j=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]);
                }
            }
            return max(max(g[n-1][0],g[n-1][1]),g[n-1][2]);
        }
    };

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

[188. 买卖股票的最佳时机 IV][188. _ IV]

### 题目描述： ###

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

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

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

### 解题思路： ###

跟上面那题一样！

### 解题代码： ###

class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
     int n=prices.size();
            vector<vector<int>>f(n,vector<int>(k+1,-0x3f3f3f));
            vector<vector<int>>g(n,vector<int>(k+1,-0x3f3f3f));
            f[0][0]=-prices[0];
            g[0][0]=0;
            int j=0;
            for(int i=1;i<n;i++)
            {
                for(int j=0;j<=k;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]);
                }
            }
            int ret=0;
            for(int i=0;i<=k;i++)
            ret=ret>g[n-1][i]?ret:g[n-1][i];
            return ret;
        }
    };

###  ###

[123. _ III]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
[2b8741e31d7a4defad31519be575613c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/ab2f23a766e34e0e90a29f9e0e7e741f.png
[188. _ IV]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
[3e3cce67457243888d6543723ad7cce5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/5fc2a80453334331b03d1662f6202c67.png