【学会动态规划】环形子数组的最大和（20）

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：918. 环形子数组的最大和 - 力扣（LeetCode）

这道题目巴拉巴拉说了一大堆好像很玄乎的东西，我们不管他，

抓住题目的核心是要找子数组，那找子数组的规则是什么呢？

我们直接通过看示例来解读：

通过示例二，我们可以看出什么叫做环形数组，他的头和尾是相连的，

所以 5 和 5 可以组成一个子数组。

那我们该怎么做这道题呢？

我们可以将它拆解成两个子问题：

1. 就是正常求他的最大子数组：

2. 因为环形数组的原因，我们可以将首尾相连的情况转化成求最小子数组和的情况：

2. 算法原理

1. 状态表示

根据我们上面分析的两种情况，其实就可以氛围两种状态表示：

f [ i ] 表示以 i 为结尾的所有子数组的最大和

g [ i ] 表示以 i 为结尾的所有子数组的最小和

2. 状态转移方程

然后每个状态表示有两种情况，一个种情况是自己，一种情况是自己加上上一个位置的最大/小和

所以他们的状态转移方程是：

f [ i ] = max( nums[ i ]，nums[ i ] + f [ i - 1 ] )

g [ i ] = min( nums[ i ]，nums[ i ] + g[ i - 1] )

3. 初始化

初始化时为了防止越界，多加一格然后初始化成0即可

4. 填表顺序

从左往右

5. 返回值

max( f 数组的最大值，sum - g 数组的最小值 )

3. 代码编写

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        auto g = f;
        for(int i = 1; i <= n; i++) {
            f[i] = max(nums[i - 1], nums[i - 1] + f[i - 1]);
            g[i] = min(nums[i - 1], nums[i - 1] + g[i - 1]);
        }
        int fmax = INT_MIN;
        int gmin = INT_MAX;
        int sum = 0;
        for(int i = 1; i <= n; i++) fmax = max(fmax, f[i]);
        for(int i = 1; i <= n; i++) gmin = min(gmin, g[i]);
        for(auto s : nums) sum += s;
        return fmax < 0 ? fmax : max(fmax, sum - gmin);
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~