LeetCode 918.环形数组的最大和

题目链接

思路

思路和LeetCode 53.最大子数组和类似
在原题基础上，先求中间一段最大子数组和ans1，容易知道ans1是不跨越原点的最大值
然后再求一个跨越原点的最大值
这个思路和上面的反过来，先求中间一段最小子数组和ans2，然后用总和减去该最小子数组和，得到的即是跨越两边的最大值sum[n] - ans2
最后两者取最大值返回max(ans1, sum[n] - ans2);

注意一个特殊情况，当整个数组全为负数的时候，最小子数组和为整个数组的和，会导致返回的值为0，此时取得是一个空的子数组，但是题目要求要的是一个非空子数组的和，所以要判断一下左右边界

代码

public class Solution {
    public int MaxSubarraySumCircular(int[] nums) {
        int[] sum = new int [nums.Length + 1];
        for (int i = 1; i < sum.Length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int min = sum[0], ans1 = int.MinValue;
        for (int i = 1; i < sum.Length; i++) {
            ans1 = Math.Max(ans1, sum[i] - min);
            min = Math.Min(sum[i], min);
        }
        int max = sum[0], ans2 = int.MaxValue, l = 0, r = 0, maxIndex = 0;
        for (int i = 1; i < sum.Length; i++) {
            if (ans2 > sum[i] - max) {
                r = i;
                l = maxIndex;
                ans2 = sum[i] - max;
            }
            if (sum[i] > max) {
                max = sum[i];
                maxIndex = i;
            }
        }
        if (l == 0 && r == sum.Length - 1) {
            return ans1;
        }
        return Math.Max(ans1, sum[sum.Length - 1] - ans2);
    }
}