算法刷题系列（四十八）：线性 DP——从前缀状态递推当前位置

算法刷题系列（四十八）：线性 DP——从前缀状态递推当前位置

线性动态规划常沿数组从左到右推进。每一步只依赖已经处理过的前缀状态，因此可以在扫描当前位置时更新答案，有时甚至不必保存整张 DP 表。

本文求整数数组的非空连续子数组最大和。设 ending[i] 是必须以位置 i 结尾的最大子数组和，则只有两种选择：把 values[i] 单独作为新子数组，或接在以 i-1 结尾的最优子数组后面：

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

全局答案是所有 ending[i] 中的最大值。这就是 Kadane 算法，也是从已完成前缀递推当前位置的典型线性 DP。

为什么只保留一个前缀状态

如果 ending[i - 1] 是负数，把它接到当前位置只会降低总和；重启子数组就更好。若它非负，接上当前值不会比单独开始更差。因此比较上述两种情况已经覆盖最优选择。

循环不变量：处理完索引 i 后，ending 等于所有以 i 结尾的非空连续子数组中的最大和；best 等于整个已处理前缀所有非空子数组的最大和。更新结束时，两个不变量继续成立。

手动推演

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

当前值	以当前位置结尾的最优和	前缀最优
-2	-2	-2
1	1	1
-3	-2	1
4	4	4
-1	3	4
2	5	5
1	6	6
-5	1	6
4	5	6

最大和为 6，对应子数组 [4, -1, 2, 1]。

Java 实现

public class Main {
    static long maxSubarraySum(int[] values) {
        if (values == null || values.length == 0) {
            throw new IllegalArgumentException("a non-empty array is required");
        }
        long ending = values[0];
        long best = ending;
        for (int i = 1; i < values.length; i++) {
            ending = Math.max((long) values[i], ending + values[i]);
            best = Math.max(best, ending);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxSubarraySum(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4})); // 6
        System.out.println(maxSubarraySum(new int[]{-7, -2, -5})); // -2
    }
}

Python 实现

def max_subarray_sum(values: list[int]) -> int:
    if values is None or not values:
        raise ValueError("a non-empty array is required")
    ending = best = values[0]
    for value in values[1:]:
        ending = max(value, ending + value)
        best = max(best, ending)
    return best

assert max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_subarray_sum([-7, -2, -5]) == -2
assert max_subarray_sum([5]) == 5
assert max_subarray_sum([0, 0]) == 0

复杂度、边界与扩展

时间 O(n)，额外空间 O(1)。本题定义子数组必须非空，所以全负数组的答案是其中最大的单个元素，不能把初始答案设为 0。空数组没有非空子数组，代码明确抛出异常；若题目允许空子数组，应改变题意对应的初始化和返回规则。Java 用 long 累加，仍应确认输入范围内不会溢出。

若还要返回区间端点，可以在 ending 重启时记录当前起点，在 best 严格变大时保存起止位置。其他线性 DP 也可用相同套路：先定义“以当前位置结尾”或“前 i 项”的含义，推导依赖关系，再检查边界和状态是否需要全量保存。不要只看到相邻递推就直接套公式；状态必须足以描述未来所需信息。

小结

线性 DP 的关键是给状态一个精确含义。Kadane 算法把“以当前位置结尾的最优值”从前一位置递推，并用全局变量聚合前缀最优结果，最终以一次扫描、常数额外空间解决最大子数组和。