力扣AC：环形子数组的最大和 - 动态规划

题目链接

环形子数组的最大和

题目描述

实现代码

思路：对于环形数组，其最大和就分为两种情况：

1. 无环的最大子数组和；
2. 有环的最大子数组和；

而对于有环的最大子数组和，其为首尾相接，因此我们找到无环的原始数组的最小子数组和，用数组元素的和减去该最小子数组和，即为第二种情况的解，两个进行对比取最大即可；

考虑极端情况，如果数组里的所有元素都为负数，那么就去最大元素即可，因此可以加一个数组最大元素的标记；

实现代码如下：

class Solution {
      public int maxSubarraySumCircular(int[] A) {
        int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
        for (int a : A) {
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + a, a);
            minSum = Math.min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}