給定一個整數陣列
nums，找出連續子陣列（至少包含一個元素）的最大和。
Example:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 (子陣列 [4,-1,2,1])
Intuition
TIP
Kadane’s Algorithm：維護當前子陣列和，如果變成負數就重新開始。
- 核心觀察：如果前面的累計和是負數，那它只會拖累後面的元素，不如從當前元素重新開始
currentSum = max(nums[i], currentSum + nums[i])- 用一個變數追蹤全域最大值
Approaches
1. Brute Force (all subarrays) — O(n^2) / O(1)
- Idea: 枚舉所有起點和終點，計算每個子陣列的和。
- Time:
O(n^2) - Space:
O(1)
class Solution {
fun maxSubArray(nums: IntArray): Int {
var maxSum = Int.MIN_VALUE
for (i in nums.indices) {
var currentSum = 0
for (j in i until nums.size) {
currentSum += nums[j]
maxSum = maxOf(maxSum, currentSum)
}
}
return maxSum
}
}⭐ 2. Kadane's Algorithm（Greedy） — O(n) / O(1)
- Idea: 遍歷陣列，維護當前連續子陣列的和。若
currentSum加上當前元素還不如當前元素本身，就從當前元素重新開始。 - Time:
O(n) - Space:
O(1)
class Solution {
fun maxSubArray(nums: IntArray): Int {
var currentSum = nums[0]
var maxSum = nums[0]
for (i in 1 until nums.size) {
currentSum = maxOf(nums[i], currentSum + nums[i])
maxSum = maxOf(maxSum, currentSum)
}
return maxSum
}
}Note: Divide & Conquer
- Idea: 將陣列分成左右兩半，最大子陣列要麼在左半、右半，或跨越中點。遞迴求解。
- Time:
O(n log n) - Space:
O(log n)遞迴深度
class Solution {
fun maxSubArray(nums: IntArray): Int {
return divideAndConquer(nums, 0, nums.size - 1)
}
private fun divideAndConquer(nums: IntArray, left: Int, right: Int): Int {
if (left == right) return nums[left]
val mid = left + (right - left) / 2
val leftMax = divideAndConquer(nums, left, mid)
val rightMax = divideAndConquer(nums, mid + 1, right)
var leftSum = Int.MIN_VALUE
var sum = 0
for (i in mid downTo left) {
sum += nums[i]
leftSum = maxOf(leftSum, sum)
}
var rightSum = Int.MIN_VALUE
sum = 0
for (i in mid + 1..right) {
sum += nums[i]
rightSum = maxOf(rightSum, sum)
}
return maxOf(leftMax, rightMax, leftSum + rightSum)
}
}🔑 Takeaways
- Pattern: Kadane’s Algorithm — 「負數前綴和一定不值得保留」的貪心策略
- Key trick: 這是面試中最常考的貪心/DP 題之一；可擴展到最大子矩陣和（2D Kadane）