问题定义

给定一个包含正数和负数的一维数组 $$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 最大子段和