动态规划：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);
    }
};