918. Maximum Sum Circular Subarray #

Problem #

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

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

Example 1:

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

Example 2:

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

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

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

Note:

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

Problem Summary #

Given a circular array C represented by an integer array A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning to form a circle. (Formally, when 0 <= i < A.length, C[i] = A[i], and when i >= 0, C[i+A.length] = C[i].)

In addition, a subarray may contain each element in the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there do not exist i <= k1, k2 <= j such that k1 % A.length = k2 % A.length.)

Note:

• -30000 <= A[i] <= 30000
• 1 <= A.length <= 30000

Solution Approach #

• Given a circular array, find the maximum sum of a contiguous subarray in this circular array.
• The first idea that comes to mind after seeing this problem is to concatenate this array with itself, and then find the maximum sum of a contiguous subarray in these two arrays. This approach is wrong. For example, for the array [5,-3,5], it would produce a result of 7, but the actual result is 10. So how should this problem be solved? With careful analysis, we can see that the maximum contiguous subarray sum of a circular array has two cases. The first case is that this contiguous segment appears directly within the array, with no circular connection. This case is relatively simple: use the kadane algorithm (which is also a dynamic programming idea), and the result can be found in O(n) time complexity. The second case is that this contiguous segment appears across the boundary of the array, meaning the head and tail are connected. To find such a contiguous segment, we can think in reverse. If we want to find a cross-boundary contiguous segment, then the remaining part of the array is a non-cross-boundary contiguous segment. If we want the sum of the cross-boundary segment to be maximum, then the sum of the remaining contiguous segment should be minimum. If we can find the maximum contiguous subarray sum in the array formed by taking the opposite of each element, then conversely we can find the minimum contiguous subarray sum in the original array. For example: [1，2，-3，-4，5]; taking the opposite of each element gives [-1，-2，3，4，-5]. The maximum contiguous subarray sum in the constructed array is 3 + 4 = 7. Since the signs were inverted, we can conclude that the minimum contiguous subarray sum in the original array is -7. Therefore, the maximum cross-boundary contiguous subarray is the remaining segment [1,2,5].
• There are also some boundary cases, such as [1，2，-2，-3，5，5，-4，6] and [1，2，-2，-3，5，5，-4，8], so we still need to compare the values of case one and case two. The maximum of the two is the final maximum sum of a contiguous subarray in the circular array.

Code #

package leetcode

import "math"

func maxSubarraySumCircular(nums []int) int {
	var max1, max2, sum int

	// case: no circulation
	max1 = int(math.Inf(-1))
	l := len(nums)
	for i := 0; i < l; i++ {
		sum += nums[i]
		if sum > max1 {
			max1 = sum
		}
		if sum < 1 {
			sum = 0
		}
	}

	// case: circling
	arr_sum := 0
	for i := 0; i < l; i++ {
		arr_sum += nums[i]
	}

	sum = 0
	min_sum := 0
	for i := 1; i < l-1; i++ {
		sum += nums[i]
		if sum >= 0 {
			sum = 0
		}
		if sum < min_sum {
			min_sum = sum
		}
	}
	max2 = arr_sum - min_sum

	return max(max1, max2)
}

func max(nums ...int) int {
	max := int(math.Inf(-1))
	for _, num := range nums {
		if num > max {
			max = num
		}
	}
	return max
}