动态规划：918. 环形子数组的最大和

个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

总结

以上就是我对于环形子数组的最大和的理解。感谢支持！！！