Ricky.L的随笔
0%

LeetCode.918.环形子数组的最大和（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.918.环形子数组的最大和（中等）

给定一个由整数数组 A 表示的环形数组 C，求 C 的非空子数组的最大可能和。

在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）

此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

题解

环形数组跟非环形数组的区别是什么？

环形数组中最终求得的最大和子数组有两种情况

  1. 数组A的首尾元素不会连接
  2. 数组A的首尾元素会连接

数组A的首尾元素不会连接的情况如何求解？

第1种情况就是非环形数组的普通求法，参与计算的区间为[0, n - 1]

数组A的首尾元素会连接的情况如何求解？

第2种情况不好用非环形数组的方法求解，实际观察结果可以得到等价情况：先求出中间部分的子数组的最小和，再用整个数组A的和减去中间的最小和就是两端首尾相连的子数组的最大和。
这时只在数组A的[1, n - 2]区间求解，这才能保证首尾不连接。

代码（kotlin）

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
31
32
33
34
class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        if (n == 1) return nums[0]

        fun getMaxSumInLinearCase(): Int {
            var maxSum = nums[0]
            var pre = 0
            for (i in 0 until n) {
                val cur = maxOf(pre + nums[i], nums[i])
                maxSum = maxOf(maxSum, cur)
                pre = cur
            }
            return maxSum
        }

        fun getMinSumInCyclicCase(): Int {
            var pre = 0
            var minSum = nums[1]
            for (i in 1..(n - 2)) {
                val cur = minOf(pre + nums[i], nums[i])
                minSum = minOf(minSum, cur)
                pre = cur
            }
            return minSum
        }

        return maxOf(
            getMaxSumInLinearCase(), 
            nums.sum() - getMinSumInCyclicCase()
        )
    }
}