53. Maximum Subarray

Medium

Description

給定一個整數陣列 nums，找出連續子陣列（至少包含一個元素）的最大和。

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 (子陣列 [4,-1,2,1])

Intuition#

Kadane’s Algorithm：維護當前子陣列和，如果變成負數就重新開始。

核心觀察：如果前面的累計和是負數，那它只會拖累後面的元素，不如從當前元素重新開始
currentSum = max(nums[i], currentSum + nums[i])
用一個變數追蹤全域最大值

Approaches#

1: 暴力（枚舉所有子陣列）#

概念: 枚舉所有起點和終點，計算每個子陣列的和。
時間複雜度: O(n^2)
空間複雜度: 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）#

概念: 遍歷陣列，維護當前連續子陣列的和。若 currentSum 加上當前元素還不如當前元素本身，就從當前元素重新開始。
時間複雜度: O(n)
空間複雜度: 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
    }
}

補充：分治法

概念: 將陣列分成左右兩半，最大子陣列要麼在左半、右半，或跨越中點。遞迴求解。
時間複雜度: O(n log n)
空間複雜度: 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 — 「負數前綴和一定不值得保留」的貪心策略
關鍵技巧: 這是面試中最常考的貪心/DP 題之一；可擴展到最大子矩陣和（2D Kadane）