学完前面的算法题，相信大家的水平定是有所提升，那么今天我们来点难题开一下刀
第一题
题目链接
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
const int INF = 0x3f3f3f3f;
int n = prices.size();
//细节处理
k = min(k,n / 2);
//建表
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; 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][j], f[i - 1][j - 1] + prices[i]);
}
}
int res = 0;
for(int j = 0; j <= k; j++)
{
res = max(g[n - 1][j], res);
}
return res;
}
};
第二题
题目链接
123. 买卖股票的最佳时机 III - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int INF = 0x3f3f3f3f;
int n = prices.size();
//建表
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 <= 2; 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)
g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
int res = 0;
for(int j = 0; j <= 2; j++)
{
res = max(res, g[n - 1][j]);
}
return res;
}
};
相信看到这里的小伙伴一定会有疑问，这两题的代码咋感觉差不多呢，是的博主也发现了，但是代码就是这样的
第三题
题目链接
题目解析
代码原理
代码编写
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
//建表
vector<int> dp(n + 1);
//初始化
dp[0] = 0;//这里可以省略，因为vector会初始化为0
//填表
int ret = -0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
ret = max(ret, dp[i]);
}
return ret;
}
};
本篇文章的内容就先到这里，我们下期文章再见！！！！
记得一键三联哦！！！
