一、題目解析

聽著有點復雜，這里一圖流。

?

將環形問題轉化為線性問題。

二、算法原理

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);}
};

?

?

看到最后，如果對您有所幫助還請點贊、收藏和關注，點點關注不迷路，我們下期再見！