|
学完前面的算法题，信赖大家的水平定是有所提升，那么本日我们来点难题开一下刀
第一题
标题链接
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[j] = max(f[i - 1][j], g[i - 1][j] - prices);
g[j] = g[i - 1][j];
if(j - 1 >= 0)
g[j] = max(g[j], f[i - 1][j - 1] + prices);
}
}
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[j] = max(f[i - 1][j], g[i - 1][j] - prices);
g[j] = g[i - 1][j];
if(j >= 1)
g[j] = max(g[j], f[i - 1][j - 1] + prices);
}
}
int res = 0;
for(int j = 0; j <= 2; j++)
{
res = max(res, g[n - 1][j]);
}
return res;
}
};
信赖看到这里的小同伴一定会有疑问，这两题的代码咋感觉差不多呢，是的博主也发现了，但是代码就是如许的
第三题
标题链接
53. 最大子数组和 - 力扣（LeetCode）
标题解析
代码原理
代码编写
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 = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
ret = max(ret, dp);
}
return ret;
}
};
本篇文章的内容就先到这里，我们下期文章再见！！！！
记得一键三联哦！！！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 | 
