动态规划 —— 子数组系列-环形子数组的最大和

1. 环形子数组的最大和

题目链接：

918. 环形子数组的最大和 - 力扣（LeetCode）https://leetcode.cn/problems/maximum-sum-circular-subarray/description/

2. 题目解析

3. 算法原理

状态表示：以某一个位置为结尾或者以某一个位置为起点

  

f[i]表示：以i位置为结尾的所有子树中的最大和

  

g[i]表示：以i位置为结尾的所有子树中的最小和

  

2. 状态转移方程

  

f[i]分为两种情况：1. 长度为1        nums[i]

  

                              2. 长度大于1    nums[i] + f[i-1] 

 

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

g[i]分为两种情况：

                              1. 长度为1        nums[i]

  

                              2. 长度大于1    nums[i] + g[i-1] 

  

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

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

  

我们可以在左边加上一个虚拟节点，为了不影响最终结果，那么就可以把这个虚拟节点初始化为0  

   

本题的下标映射关系：下标统一往后移动一位

  

4. 填表顺序 

  

本题的填表顺序是：从左往右

5. 返回值 ：题目要求 + 状态表示     

  

本题的返回值是：1. 找到f表里的最大值，fmax

   

                              2.找到g表里的最小值,gmin,  gmin在对比之前要先用sum - gmin再进行比较

 在这里我们要考虑数组里全是负数的情况，比如为{-1,-2,-3}，那么fmax的值就是-1，gmin的值就是三个数相加，sum - gmin的结果就为0，这样题目就不允许，所以我们要加上一个判断条件：

  

当sum和gmin相等的时候说明数组里面的值都是负数，那么就直接返回fmax,否则就返回两者相比之后的值

  

4.  代码

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值

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++)
        {
            int x=nums[i-1];//加上一个虚拟节点下标-1
            f[i]=max(x,f[i-1]+x);
            fmax=max(f[i],fmax);
            
            g[i]=min(x,g[i-1]+x);
            gmin=min(g[i],gmin);
            sum+=x;
        }
            return sum==gmin?fmax:max(fmax,sum-gmin);
    }
};

未完待续~