复习周终于结束了，这也是复习周结束后的第一篇文章，请各位小伙伴们细细品尝，废话不多说，我们开始今天的讲解。
第一题
题目链接
918. 环形子数组的最大和 - 力扣（LeetCode）
题目解析
代码原理
注意：g[i - 1]与先前讲的dp[i - 1]是一样的，即到i-1位置的最小子数组和
代码编写
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
//建表
vector<int> f(n + 1);
auto g = f;
//初始化
f[0] = -0x3f3f3f3f,g[0] = 0x3f3f3f3f;
//填表
int sum = 0, fmax = -0x3f3f3f3f,gmin = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
fmax = max(fmax, f[i]);
g[i] = min(g[i - 1] + nums[i - 1], nums[i - 1]);
gmin = min(g[i], gmin);
sum += nums[i - 1];
}
return sum == gmin? fmax:max(fmax,sum - gmin);
}
};
第二题
题目链接
152. 乘积最大子数组 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int maxProduct(vector<int>& nums) {
int n = nums.size();
//建表
vector<int>f(n + 1);
auto g = f;
//初始化
f[0] = g[0] = 1;
int ret = -0x3f3f3f3f;
//填表
for(int i = 1; i <= n; i++)
{
f[i] = max(max(nums[i - 1], nums[i - 1] * f[i - 1]), nums[i - 1] * g[i - 1]);
g[i] = min(min(nums[i - 1], nums[i - 1] * f[i - 1]), nums[i - 1] * g[i - 1]);
ret = max(f[i], ret);
}
return ret;
}
};
第三题
题目链接
1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）
题目解析
代码原理
代码编写
class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
//建表
vector<int> f(n + 1);
auto g = f;
//初始化
g[0] = f[0] = 0;
int res = -0x3f3f3f3f;
for(int i = 1; i <= n; i++)
{
if(nums[i - 1] > 0)
{
f[i] = f[i - 1] + 1;
g[i] = g[i - 1] == 0? 0: g[i - 1] + 1;
}
else if(nums[i - 1] < 0)
{
g[i] = f[i - 1] + 1;
f[i] = g[i - 1] == 0? 0: g[i - 1] + 1;
}
res = max(res, f[i]);
}
return res;
}
};
那么本题的难点就是最后的那一部分，博主在这里也是出了点小事故，那么这题看似复杂其实自己画图+思考后也可以理解。
那么这题有没有其他方法呢？当然是有的，那么预知后事如何，且听博主下回分析。
