Description
給定一個環形整數陣列
nums，找出環形子陣列的最大和。環形子陣列表示陣列可以從尾部接回頭部。
Example:
Input: nums = [1,-2,3,-2] Output: 3
Intuition#
最大環形子陣列和 = max(普通最大子陣列和, 總和 - 最小子陣列和)。
- 情況一：最大子陣列不跨越邊界 → 直接用 Kadane’s 求最大
- 情況二：最大子陣列跨越邊界 → 等於總和減去中間的最小子陣列
- 特殊情況：如果所有元素都是負數，最小子陣列 = 全部，此時取最大子陣列
Approaches#
1: 兩次 Kadane’s#
- 概念: 分別求最大子陣列和、最小子陣列和，答案取兩者中較大的。
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun maxSubarraySumCircular(nums: IntArray): Int {
var maxSum = nums[0]; var curMax = 0
var minSum = nums[0]; var curMin = 0
var total = 0
for (num in nums) {
curMax = maxOf(curMax + num, num)
maxSum = maxOf(maxSum, curMax)
curMin = minOf(curMin + num, num)
minSum = minOf(minSum, curMin)
total += num
}
// 所有元素都是負數時，total - minSum = 0，應取 maxSum
return if (total == minSum) maxSum else maxOf(maxSum, total - minSum)
}
}⭐2: 一次遍歷（同上，最簡潔寫法）#
- 概念: 同時執行兩個 Kadane’s（一個求最大、一個求最小），一次遍歷完成。
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun maxSubarraySumCircular(nums: IntArray): Int {
var totalSum = 0
var maxSum = Int.MIN_VALUE; var curMax = 0
var minSum = Int.MAX_VALUE; var curMin = 0
for (num in nums) {
totalSum += num
curMax = maxOf(curMax + num, num)
maxSum = maxOf(maxSum, curMax)
curMin = minOf(curMin + num, num)
minSum = minOf(minSum, curMin)
}
return if (maxSum < 0) maxSum else maxOf(maxSum, totalSum - minSum)
}
}🔑 Takeaways#
- Pattern: 環形問題拆分 — 跨越邊界的最大 = 總和 - 不跨越邊界的最小
- 關鍵技巧: 雙 Kadane’s 同時求最大和最小；全負數情況需特殊處理