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

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

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

题解：

1.状态表示：f[i]表示以i位置元素为结尾的连续子数组中，最大和连续子数组的元素和

                     g[i]表示以i位置元素为结尾的连续子数组中，最小和连续子数组的元素和

2.状态转移方程：f[i]=max(f[i-1]+nums[i],nums[i])

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

以i位置元素为结尾的连续子数组有两种情况：一是仅有i位置元素组成一个子数组；二是由i位置元素和前面的元素组成一个子数组

3.初始化：f[0]=nums[0] 根据状态转移方程，以nums[0]为结尾的子数组只有情况一

                 g[1]=nums[1] g表要去除首尾元素初始化，所以初始化的第一个元素是g[1]

4.填表顺序：从左向右填写

5.返回值：f表中最大的元素（即不跨越首尾元素的连续子数组的最大和）和sum-g表中最小元素（即跨越首尾元素的连续子数组的最大和）的较大值

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {//f[i]表示以i位置元素为结尾的所有连续子数组中的最大子数组和//g[i]表示以i位置元素为结尾的所有连续子数组中的最小子数组和//f[i]=max(f[i-1]+nums[i],nums[i])//g[i]=min(g[i-1]+nums[i],nums[i])//环形数组中的连续子数组有两种情况：1.不跨越首尾元素2.跨越首尾元素//对于不跨越首尾元素的情况只需要按照《最大子数组和》问题求即可//对于跨越首尾元素的情况需要反向思考：求不跨越首尾元素情况的最小子数组和，再用总元素和减去//比较两种情况，得到最大和size_t n=nums.size();//处理边界条件if(n==1) return nums[0];//创建dp表vector<int> f(n);auto g=f;//初始化f[0]=nums[0];//g[0]=nums[0];g[1]=nums[1];//填表for(int i=1;i<n;++i)f[i]=max(f[i-1]+nums[i],nums[i]);//有一种特殊情况：如果nums表中全部是负数，那么最小子数组和就是总元素和sum//而sum-sum为0，即跨越首尾元素的最大子数组和为0，显然是不正确的//所以求最小连续子数组和要去除首尾元素for(int i=2;i<n-1;++i)g[i]=min(g[i-1]+nums[i],nums[i]);//返回值int ans1=INT_MIN;int ans2=INT_MAX;for(auto e:f) if(e>ans1) ans1=e;for(auto e:g) if(e<ans2) ans2=e;int sum=0;for(auto e:nums) sum+=e;return max(ans1,sum-ans2);}
};