动态规划-918.环形子数组的最大和-力扣(LeetCode)

一、题目解析

听着有点复杂，这里一图流。

 

将环形问题转化为线性问题。

二、算法原理

1.状态表示

2.状态转移方程

 

 

详细可以移步另一篇博客，53. 最大子数组和 - 力扣（LeetCode）

3.初始化

由于计算中需要用到f[i-1]和g[i-1]的值，所以可以直接初始化f[0]和g[0]的值，也可以加上一个虚拟节点，用于初始化。

4.填表顺序

从左往右，两个表一起填，保证所需值已计算。

5.返回值

需要返回f中和sum-g中两者的最大值

思考与实操同等重要，在思考后去实操，链接： 

三、 代码示例

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n = nums.size();vector<int> f(n+1),g(n+1);int sum = 0;for(int i = 1;i<=n;i++){f[i]=max(nums[i-1],f[i-1]+nums[i-1]);g[i]=min(nums[i-1],g[i-1]+nums[i-1]);sum+=nums[i-1];}int f_max = f[1],g_min = g[1];for(int i = 2;i<=n;i++){if(f[i]>f_max) f_max = f[i];if(g_min>g[i]) g_min = g[i];}return sum == g_min ? f_max : max(f_max,sum-g_min);}
};

 

 

看到最后，如果对您有所帮助还请点赞、收藏和关注，点点关注不迷路，我们下期再见！