918. Maximum Sum Circular Subarray 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int[] f = new int[nums.length]; // 定义 f[i] 为以 nums[i] 结尾的最大子数组和
        int[] g = new int[nums.length]; // 定义 g[i] 为以 nums[i] 结尾的最小子数组和

        f[0] = g[0] = nums[0];

        int maxSubArraySum = f[0];
        int minSubArraySum = g[0];

        for (int i = 1; i < nums.length; i++) {
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            g[i] = Math.min(g[i - 1] + nums[i], nums[i]);
            maxSubArraySum = Math.max(maxSubArraySum, f[i]);
            minSubArraySum = Math.min(minSubArraySum, g[i]);
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum == minSubArraySum) {
            // 处理 nums 全为负数的场景，因为题目要求返回 nums 的非空子数组的最大可能和
            return maxSubArraySum;
        }

        return Math.max(maxSubArraySum, sum - minSubArraySum);
    }
}

References

918. Maximum Sum Circular Subarray