算法刷题系列（六十一）：最大子数组和——从枚举到 Kadane 算法

算法刷题系列（六十一）：最大子数组和——从枚举到 Kadane 算法

旧笔记记录了“最大子列和”题目，但没有展开算法。本篇将问题整理成完整推导：从枚举所有连续区间出发，观察以当前位置结尾的最优解只依赖前一个位置，从而得到 Kadane 算法。

一、明确子数组与答案约定

给定非空整数数组，求一个非空连续子数组，使其元素和最大，并返回最大和。若还需要起止下标，可以在更新最优值时一并保存。

例如：

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

答案是 [4, -1, 2, 1]，和为 6。连续性意味着不能挑出分散元素拼成答案。

二、动态规划状态

定义：

endHere[i] = 必须以 i 结尾的最大连续子数组和

以 i 结尾的最优子数组只有两种可能：

1. 从 values[i] 重新开始；
2. 把 values[i] 接到以 i-1 结尾的最优区间后面。

因此：

endHere[i] = max(values[i], endHere[i - 1] + values[i])
answer = max(endHere[i])

若之前的和为负，接上它只会让当前值变小，因此应该从当前位置重新开始。只保存前一状态即可把空间降到 O(1)。

三、Java 实现并返回区间

public class MaximumSubarray {
    public static final class Result {
        public final long sum;
        public final int start;
        public final int end;

        Result(long sum, int start, int end) {
            this.sum = sum;
            this.start = start;
            this.end = end;
        }
    }

    public static Result maximumSubarray(int[] values) {
        if (values == null || values.length == 0) {
            throw new IllegalArgumentException("values must be non-empty");
        }

        long current = values[0];
        long best = values[0];
        int currentStart = 0;
        int bestStart = 0;
        int bestEnd = 0;

        for (int i = 1; i < values.length; i++) {
            if (current < 0) {
                current = values[i];
                currentStart = i;
            } else {
                current += values[i];
            }
            if (current > best) {
                best = current;
                bestStart = currentStart;
                bestEnd = i;
            }
        }
        return new Result(best, bestStart, bestEnd);
    }
}

初始化为首元素而不是 0，保证全负数输入时仍返回一个非空区间。

四、Python 实现

def maximum_subarray(values: list[int]) -> tuple[int, int, int]:
    if values is None or not values:
        raise ValueError("values must be non-empty")

    current = best = values[0]
    current_start = best_start = best_end = 0
    for index in range(1, len(values)):
        if current < 0:
            current = values[index]
            current_start = index
        else:
            current += values[index]
        if current > best:
            best = current
            best_start = current_start
            best_end = index
    return best, best_start, best_end

assert maximum_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == (6, 3, 6)
assert maximum_subarray([-8, -3, -6]) == (-3, 1, 1)
assert maximum_subarray([0, 0]) == (0, 0, 0)

Python 返回闭区间下标 (start, end)；取值时用 values[start:end + 1]。若 API 更适合半开区间，可以返回 (start, end + 1)，并统一全篇约定。

五、复杂度与其他解法

• Kadane：时间 O(n)，除输出区间信息外额外空间 O(1)。
• 枚举所有起点和终点：O(n²)；若每次重算区间和，可能达到 O(n³)。
• 前缀和可以让固定区间求和为 O(1)，但枚举区间仍有 O(n²) 个。
• 分治也能在 O(n log n) 时间求最大子数组和，适合作为理解“跨越中点区间”的练习。

六、边界与常见错误

1. 全负数组返回 0：这相当于允许空子数组；若题目要求非空，必须从第一个元素初始化。
2. 只保存最大和，错过区间下标：维护当前候选起点，并在最优值更新时保存端点。
3. 把子序列当子数组：子数组必须连续。
4. 整数累加溢出：Java 可使用 long，并根据输入约束确认累计和范围。
5. 和相同时随意改变答案：若题目规定优先更短或更靠左的区间，需要把平局规则写进比较条件。

与系列其他篇章的连接

本题是第 48 篇线性 DP的经典实例：状态只依赖前一个位置。若需要许多静态区间和查询，可转用前缀和。

小结

最大子数组和的关键是明确“必须以当前位置结尾”的状态。若延续旧区间比重新开始更优就接上，否则丢弃负贡献，从而用一次扫描求解。