个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》《C++》《算法》
文章目录
- 前言
- 一、题目解析
- 二、解题思路
- 解题思路
- 状态表示
- 状态转移方程
- 初始化
- 填表顺序
- 返回值
- 三、代码实现
- 总结
前言
本篇文章仅是作为小白的我的一些理解，，如果有错误的地方，希望大佬们指出。
918. 环形子数组的最大和
一、题目解析
求环型数组中连续子数组最大和。
二、解题思路
解题思路
关于子数组的最大和，其有两种情况。
对于情况1而言，我们只需要正常使用dp求最大子数组和即可。
对于情况2而言，如果我们使用前缀和 与 后缀和 求和来求最大子数组和就相对麻烦，但如果我们先求最小子数组和呢？
情况二：求最大子数组和，就可以转换为数组和(sum) – 最小子数组和。
状态表示
该题的状态表示：经验(以该位置为终点 / 以该位置为起点) + 题目要求
那么对于情况1记为 f() ，f [ i ]表示以 i 位置为终点的所以子数组的最大和。
那么对于情况2记为 g()，g [ i ]表示以 i 位置为终点的所以子数组的最小和。
状态转移方程
情况1
对于在数组 i 位置的元素，我们可以将其分成两个状态。
即 f [i]的长度等于1，和 f [i]的长度大于1。
当 f [i]的长度等于1时，此时子数组最大和不就是该元素的大小，即f [i] = nums[i]
当 f [i]的长度大于1时，此时子数组最大和不就是 之前子数组最大和(f[i-1]) + 该元素大小，即f[i] = f[i-1] + nums[i]
那么我们对这两种情况取最大值即可得 f [ i ] 的状态转移方程。
情况2
和情况1类似，对于情况2，我们同样可以以 i位置，分成两种状态。
即 g [i]的长度等于1，和 g [i]的长度大于1。
当 g [i]的长度等于1时，此时子数组最小和不就是该元素的大小，即g [i] = nums[i]
当 g [i]的长度大于1时，此时子数组最小和不就是 之前子数组最小和(g[i-1]) + 该元素大小，即g[i] = g[i-1] + nums[i]
那么我们对这两种状态取最小值，既可以得到 g [i]的状态转移方程
初始化
我们要求 f [i]就要先知道 f [i -1]，但如果当 i = 0时，f [i-1]就会越界。那么我们虚拟一块空间，将整个 f[i] 后移一个位置。如下所示：
如果我们进行这样的操作，有两点需要注意。
- 如何填写 f[0]保证后续填表结果正确？
只要f[0] = 0即可，毕竟f[1] = max(f[0], f[0]+nums[0])此时f[0] == f[0] + nums[0] - 映射关系
因为整个f[i]后移了一个，所以f[i] 所对应的元素 nums[i]相对前移了，即f[i] 与 nums[i-1]的元素相对应。
填表顺序
要求f[i]，就要先知道f[i-1]，那么我们就要从前向后遍历数组nums，来填表。
返回值
我们只需要 返回情况1 与 情况2 的最大值即可。
但对于{-1, -2, -3, -4}而言，情况2 的值是：sum(-10) – gmin(-10)等于0，情况1 的值是：fmax(-1)。那么返回值就是0，结果错误。所以要先判断gmin == sum，如果相等，表示此时数组全是负数，返回fmax即可。如果不相等，返回情况1 与 情况2 的最大值即可。
三、代码实现
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
vector<int> f(n+1), g(n+1);
int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
for(int i = 1; i <= n; i++)
{
f[i] = max(f[i-1] + nums[i-1], nums[i-1]);
fmax = max(f[i], fmax);
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);
}
};
总结
以上就是我对于环形子数组的最大和的理解。感谢支持！！！
文章出处登录后可见！
