1. 题目链接:918. 环形子数组的最大和
2. 题目描述:
给定一个长度为
n
的环形整数数组nums
,返回nums
的非空 子数组 的最大可能和 。环形数组 意味着数组的末端将会与开头相连呈环状。形式上,
nums[i]
的下一个元素是nums[(i + 1) % n]
,nums[i]
的前一个元素是nums[(i - 1 + n) % n]
。子数组 最多只能包含固定缓冲区
nums
中的每个元素一次。形式上,对于子数组nums[i], nums[i + 1], ..., nums[j]
,不存在i <= k1, k2 <= j
其中k1 % n == k2 % n
。示例 1:
输入:nums = [1,-2,3,-2] 输出:3 解释:从子数组 [3] 得到最大和 3
示例 2:
输入:nums = [5,-3,5] 输出:10 解释:从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3:
输入:nums = [3,-2,2,-3] 输出:3 解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示:
n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
3. 解法(动态规划)
3.1 算法思路:
1. 状态表示:
f[i]
表示:以i
为结尾的所有子数组中的最大和
g[i]
表示:以i
做结尾的所有子数组中和的最和
2. 状态转移方程:
3. 初始化:
可以在最前面加上一个辅助结点,帮助我们完成初始化。使用这种技巧要注意两点:
- 辅助结点里面的值要保证后续填表是正确的
- 下标的映射关系
4. 填表顺序:
根据状态转移方程,填表顺序为从左往右
5. 返回值
- 先找到
f
表里面的最大值->fmax
- 再找到
g
表里面的最小值->gmin
- 统计所有元素的和->
sum
- 返回
sum==gmin?fmax:max(fmax,sum-gmin)
3.2 C++算法代码:
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
// 获取数组长度
int n = nums.size();
// 初始化两个辅助数组f和g,长度为n+1
vector<int> f(n + 1), g(n + 1);
// 初始化最大子数组和fmax、最小子数组和gmin、数组元素和sum
int fmax = INT_MIN, gmin = INT_MAX, sum = 0;
// 遍历数组
for (int i = 1; i <= n; i++) {
// 获取当前元素值
int x = nums[i - 1];
// 更新f数组:f[i]表示以nums[i-1]结尾的最大子数组和
f[i] = max(x, x + f[i - 1]);
// 更新fmax:记录所有位置上的最大子数组和
fmax = max(fmax, f[i]);
// 更新g数组:g[i]表示以nums[i-1]结尾的最小子数组和
g[i] = min(x, x + g[i - 1]);
// 更新gmin:记录所有位置上的最小子数组和
gmin = min(gmin, g[i]);
// 更新sum:记录数组元素之和
sum += x;
}
// 如果sum等于gmin,说明整个数组都是负数,此时最大子数组和为fmax;否则,最大子数组和为fmax和sum-gmin中的较大值
return sum == gmin ? fmax : max(fmax, sum - gmin);
}
};