LeetCode 918. Maximum Sum Circular Subarray

原题链接在这里：https://leetcode.com/problems/maximum-sum-circular-subarray/description/

题目：

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Example 1:

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Example 2:

Input: nums = [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3:

Input: nums = [-3,-2,-3]
Output: -2
Explanation: Subarray [-2] has maximum sum -2.

Constraints:

• n == nums.length
• 1 <= n <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104

题解：

To find the max sum of circular subarray, there are two contitions.

First is max sum occurs in the middle of array.

Second is max sum occurs with tail + head.

For the second part, max(prefix + suffix) = max(sum - middle part) = sum - min(middle part).

Note: when all the nums are negative, sum - min(middle part) = 0, but we can't accept empty subset. Thus when globalMax <= 0, just take the globalMax.

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int maxSubarraySumCircular(int[] nums) {
 3         if(nums == null || nums.length == 0){
 4             return 0;
 5         }
 6 
 7         int sum = 0;
 8         int n = nums.length;
 9         int localMax = 0;
10         int globalMax = nums[0];
11         int localMin = 0;
12         int globalMin = nums[0];
13         for(int num : nums){
14             localMax = Math.max(localMax + num, num);
15             globalMax = Math.max(globalMax, localMax);
16             localMin = Math.min(localMin + num, num);
17             globalMin = Math.min(globalMin, localMin);
18             sum += num;
19         }
20 
21         return globalMax > 0 ? Math.max(globalMax, sum - globalMin) : globalMax;
22     }
23 }

类似Maximum Subarray.