题意

给定一个长度为n的圆形整数数组nums，返回nums的非空子数组的最大可能之和。

循环数组意味着数组的结束与数组的开始相连接。形式上，nums[i]的下一个元素是nums[(i + 1) % n]，nums[i]的前一个元素是nums[(i - 1 + n) % n]。

一个子数组最多只能包括固定缓冲区nums的每个元素一次。形式上，对于一个子数组nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j而k1 % n == k2 % n。

思路

这道题的思路就是将计算方式分成两个部分

• 没有环的情况计算，就是一种dp，dp[i] = max(nums[i], dp[i-1]+nums[i]).
• 第二种就是收尾相接的情况
  • 先从左向右计算一个max数组 lr max[i] = max(max[i], max[i-1]+nums[i])
  • 再从右向左计算一个max数组 rl

最后计算结果就是 max = max(max, rl[i] + rl[i-1]) (0 <i < length)

const min918 = -30000

func maxSubarraySumCircular(nums []int) int {
	ans := min918
	l := len(nums)
	if l == 1 {
		return nums[0]
	}
	sub := make([]int, l)
	copy(sub, nums)
	for i := 0; i < l; i++ {
		if i != 0 {
			if sub[i-1]+sub[i] > sub[i] {
				sub[i] = sub[i-1] + sub[i]
			}
		}

		if sub[i] > ans {
			ans = sub[i]
		}
	}

	lr := make([]int, l)
	rl := make([]int, l)
	sum := make([]int, l)
	sum[0] = nums[0]
	lm := nums[0]
	for i := 1; i < l; i++ {
		sum[i] = sum[i-1] + nums[i]
		if sum[i] > lm {
			lm = sum[i]
		}
		lr[i] = lm
	}
	total := sum[l-1]
	if total > ans {
		ans = total
	}

	rm := nums[l-1]
	for i := l - 1; i > 0; i-- {
		sum[i] = total - sum[i-1]
		if rm < sum[i] {
			rm = sum[i]
		}
		rl[i] = rm
	}
	sum[0] = total
	for i := l - 1; i > 0; i-- {
		if lr[i-1]+rl[i] > ans {
			ans = lr[i-1] + rl[i]
		}
	}
	return ans
}