算法：最大子陣列和（最大子段和）問題

問題定義#

給定一個包含正數和負數的一維數組 $A[1..n]$ ，尋找一個連續子數組 $A[i..j]$ ，使得
子數組的元素和最大，即求：

$\max _{1\leq i\leq j\leq n} \sum_{k=i}^j A[k]$

並返回這個最大值。有時還需要返回這個子數組的起止位置 $i, j$

應用場景#

股票買賣分析：尋找買入和賣出時間，使利潤最大（即漲幅最大的一段時間）。

財務數據分析：尋找公司利潤最好的時間段。

圖像處理：在像素數組中找出亮度最集中的區域。

DNA 序列分析：在基因評分序列中尋找最優片段。

暴力法求解（枚舉）#

max_sum = float('-inf')
for i in range(n):
    sum = 0
    for j in range(i, n):
        sum += A[j]
        if sum > max_sum:
            max_sum = sum

有 $O(n^2)$ 個子數組。時間複雜度為 $O(n^2)$ 。子數組的和在累加中直接 $O(1)$ 求出。

分治法求解#

思路：將數組分成左右兩半，遞歸地解決左半和右半的最大子數組，然後處理跨越中間的最大子數組。分別考慮以下的三種情況：
最大子數組在左邊
最大子數組在右邊
最大子數組橫跨中點

時間複雜度
遞推式： $T(n) = 2T(n/2) + O(n)$ ，然後使用主定理求得
或直接分析可得 $O(n\log n)$

def max_subarray(A, left, right):
    if left == right:
        return A[left], left, right

    mid = (left + right) // 2

    left_sum, l_start, l_end = max_subarray(A, left, mid)
    right_sum, r_start, r_end = max_subarray(A, mid + 1, right)
    cross_sum, c_start, c_end = max_crossing_subarray(A, left, mid, right)

    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_sum, l_start, l_end
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_sum, r_start, r_end
    else:
        return cross_sum, c_start, c_end


def max_crossing_subarray(A, left, mid, right):
    sum = 0
    left_max = float('-inf')
    max_left = mid
    for i in range(mid, left - 1, -1):
        sum += A[i]
        if sum > left_max:
            left_max = sum
            max_left = i

    sum = 0
    right_max = float('-inf')
    max_right = mid + 1
    for j in range(mid + 1, right + 1):
        sum += A[j]
        if sum > right_max:
            right_max = sum
            max_right = j

    return left_max + right_max, max_left, max_right

動態規劃法#

思路：用變量 current_sum 表示以當前位置結尾的最大子數組和，如果當前元素單獨更優，就重啟子數組；否則就擴展當前子數組

迭代方程： $dp[i] = \max\{ dp[i-1] + A[i], A[i]\}$

時間複雜度： $O(n)$

current_sum = max_sum = A[0]
for i in range(1, n):
    current_sum = max(A[i], current_sum + A[i])
    max_sum = max(max_sum, current_sum)

練習題#

洛谷 P1115 最大子段和