Maximum Subarray Evolution

「找出和最大的連續子陣列」這題之所以經典，不在答案本身，而在它能用四種解法一路優化：從 O(n^3) 暴力到 O(n) 的 Kadane。每一次提速，本質都是辨識並消除重複計算——這正是動態規劃與前綴和的共同精神，看懂這條演進，比記住任何單一模板都有用。

解法一：暴力枚舉所有區間 O(n^3)

枚舉每個 (i, j) 區間，再從頭加總一次。

fun maxSub1(nums: IntArray): Int {
    var best = Int.MIN_VALUE
    for (i in nums.indices) {
        for (j in i until nums.size) {
            var sum = 0
            for (k in i..j) sum += nums[k]   // 每次重算整段和
            best = maxOf(best, sum)
        }
    }
    return best
}

瓶頸：最內層「重算整段和」是純粹的重複功。

解法二：邊延伸邊累加 O(n^2)

固定左端 i，右端 j 往右延伸時，和只要在前一步上加 nums[j]，省掉最內層迴圈。

fun maxSub2(nums: IntArray): Int {
    var best = Int.MIN_VALUE
    for (i in nums.indices) {
        var sum = 0
        for (j in i until nums.size) {
            sum += nums[j]                   // 重用上一步的和
            best = maxOf(best, sum)
        }
    }
    return best
}

解法三：分治 O(n log n)

最大子陣列要嘛全在左半、要嘛全在右半、要嘛跨越中點。前兩種遞迴解決，跨中點的情形從中點分別向左、向右各掃一次求最大延伸和，再合併。遞迴式 T(n) = 2T(n/2) + O(n)，解得 O(n log n)。

fun maxSub3(nums: IntArray, lo: Int, hi: Int): Int {
    if (lo == hi) return nums[lo]
    val mid = lo + (hi - lo) / 2
    val left = maxSub3(nums, lo, mid)
    val right = maxSub3(nums, mid + 1, hi)

    var sum = 0; var leftBest = Int.MIN_VALUE
    for (i in mid downTo lo) { sum += nums[i]; leftBest = maxOf(leftBest, sum) }
    sum = 0; var rightBest = Int.MIN_VALUE
    for (i in mid + 1..hi) { sum += nums[i]; rightBest = maxOf(rightBest, sum) }

    return maxOf(left, right, leftBest + rightBest)
}

解法四：Kadane O(n)

關鍵洞見：定義 cur 為「以當前元素結尾的最大子陣列和」。對每個元素，要嘛把它接到前面那段（前提是前面那段為正、值得接），要嘛從它自己重新開始：

cur = max(nums[i], cur + nums[i])

fun maxSubArray(nums: IntArray): Int {
    var cur = nums[0]
    var best = nums[0]
    for (i in 1 until nums.size) {
        cur = maxOf(nums[i], cur + nums[i])   // 接續 or 重啟
        best = maxOf(best, cur)
    }
    return best
}

四解對照

跨倉庫導讀

• 對應理論章節：動態規劃、遞迴與分治
• 解題提速的通用框架見本書 Problem Solving → BUD 最佳化。