Kadane算法及其在一维与二维最大子段和问题中的应用
摘要
本文系统阐述Kadane算法的核心原理、数学证明及其在一维最大子数组和、二维最大子矩阵和问题中的应用。通过严谨的数学推导与代码实现，展示该算法从一维到二维的扩展逻辑，并补充证明一维场景下前缀和方法与Kadane算法的数学等价性，为算法复习与应用提供参考。
引言
最大子段和问题是算法设计中的经典问题，其核心是在给定序列中寻找连续子序列，使其元素和最大。Kadane算法以其 $O(n)$ 的时间复杂度，成为解决一维最大子数组和问题的最优解法；通过降维思想，该算法可进一步扩展至二维最大子矩阵和问题。
一维最大子数组和问题
问题定义
给定长度为 $n$ 的整数数组 $a[1..n]$ （下标从1开始），寻找连续子数组 $a[i..j]$ （ $1 \le i \le j \le n$ ），使得其和 $S(i,j) = \sum_{k=i}^j a[k]$ 最大。若所有子数组和均为负，则返回0（对应“放弃选择”的场景）。
Kadane算法描述
状态定义
定义 $dp[j]$ 为以第 $j$ 个元素结尾的所有连续子数组的最大和。
状态转移方程
对于第 $j$ 个元素，以其结尾的连续子数组有两种选择：
-
仅包含 $a[j]$ 自身，和为 $a[j]$ ；
-
包含 $a[j]$ 及以 $j-1$ 结尾的最大子数组，和为 $dp[j-1] + a[j]$ 。
因此状态转移方程为：
$dp[j] = \max\left(a[j], dp[j-1] + a[j]\right)$
全局最大值计算
由于任意连续子数组必然以某个位置 $j$ 结尾，全局最大子数组和为：
$max\_sum = \max\left(dp[1], dp[2], \dots, dp[n]\right)$
最终结果为 $\max(max\_sum, 0)$ ，以处理全负数组的情况。
数学正确性证明
采用数学归纳法证明“ $dp[j]$ 是以 $j$ 结尾的最大子数组和”：
-
基例（ $j=1$ ）：
$dp[1] = a[1]$ ，显然成立——以第一个元素结尾的子数组只能是其自身。
-
归纳步骤（假设 $j=k$ 时成立，证明 $j=k+1$ 时也成立）：
假设 $dp[k]$ 是以 $k$ 结尾的最大子数组和。考虑以 $k+1$ 结尾的子数组：
-
若子数组仅包含 $a[k+1]$ ，和为 $a[k+1]$ ；
-
若子数组包含前面的元素，则其形式为“以 $k$ 结尾的子数组 + $a[k+1]$ ”。根据归纳假设， $dp[k]$ 是以 $k$ 结尾的最大和，因此“ $dp[k] + a[k+1]$ ”是该情况下的最大值。
因此 $dp[k+1] = \max(a[k+1], dp[k] + a[k+1])$ 成立，归纳步骤得证。
前缀和视角与Kadane算法的本质联系与等价性证明
本节将严格证明：Kadane算法在数学上与“前缀和 + 维护最小值”的方法完全等价。
前缀和定义
定义前缀和数组 $s[0..n]$ ，其中：
-
$s[0] = 0$
-
$s[j] = a[1] + a[2] + \dots + a[j] = \sum_{k=1}^j a[k]$
根据定义，任意子数组 $a[i..j]$ 的和可表示为：
$S(i,j) = s[j] - s[i-1]$
前缀和视角下的目标
对于固定的右端点 $j$ ，我们的目标是找到左端点 $i$ （ $1 \le i \le j$ ），使得 $S(i,j)$ 最大。由于 $s[j]$ 是定值，最大化 $s[j] - s[i-1]$ 等价于最小化 $s[i-1]$ 。
因此，以 $j$ 结尾的最大子数组和为：
max\_ending\_at\_j = s[j] - \min_{0 \le k \le j-1} s[k]等价性推导
我们将证明：Kadane算法中的 $dp[j]$ 与上式中的 $max\_ending\_at\_j$ 完全相等。
证明：
首先，根据前缀和定义，我们有：
$a[j] = s[j] - s[j-1]$
将Kadane的状态转移方程展开：
$dp[j] = \max\left(a[j], dp[j-1] + a[j]\right)$
根据归纳假设（或递推关系）， $dp[j-1]$ 可表示为：
$dp[j-1] = s[j-1] - \min_{0 \le k \le j-2} s[k]$
将 $a[j]$ 和 $dp[j-1]$ 代入Kadane方程的右侧第二项：
\begin{aligned}dp[j-1] + a[j] &= \left(s[j-1] - \min_{0 \le k \le j-2} s[k]\right) + \left(s[j] - s[j-1]\right) &= s[j] - \min_{0 \le k \le j-2} s[k] \end{aligned}现在看Kadane方程的右侧第一项 $a[j]$ ，它可以改写为：
$a[j] = s[j] - s[j-1]$
这对应了在 $k = j-1$ 时的取值。
因此，Kadane的取最大值操作：
$dp[j] = \max\left(s[j] - s[j-1], s[j] - \min_{0 \le k \le j-2} s[k]\right)$
可以提取公因子 $s[j]$ ，转化为：
$dp[j] = s[j] - \min\left(s[j-1], \min_{0 \le k \le j-2} s[k]\right)$
由于
\min\left(s[j-1], \min_{0 \le k \le j-2} s[k]\right) = \min_{0 \le k \le j-1} s[k]我们最终得到：
$dp[j] = s[j] - \min_{0 \le k \le j-1} s[k]$
证毕。
结论
Kadane算法与前缀和方法是同一数学本质的两种不同表现形式：
-
前缀和视角是“全局视角”，通过维护历史前缀和的最小值来计算当前最优解；
-
Kadane算法是“增量视角”或“贪心视角”，通过动态规划转移方程隐式地维护了这一最小值。
两者在时间复杂度上均为 $O(n)$ ，但Kadane算法在代码实现上通常更简洁，且无需显式存储前缀和数组。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
int current_sum = a[0];
int max_sum = a[0];
for (int i = 1; i < n; ++i) {
current_sum = max(a[i], current_sum + a[i]);
max_sum = max(max_sum, current_sum);
}
cout << max(max_sum, 0) << endl;
return 0;
}二维最大子矩阵和问题
问题定义
给定 $R \times C$ 的整数矩阵 $M$ ，寻找行和列均连续的非空子矩阵，使其元素和最大。
降维思路：二维转一维
核心思想是枚举所有连续行区间，将该区间内每一列的元素求和，压缩为一维数组，从而将二维问题转化为一维最大子数组和问题。
算法描述
-
枚举上边界 $top$ （ $0 \le top < R$ ）；
-
初始化列和数组 $col\_sum$ ，长度为 $C$ ，初始值为0；
-
枚举下边界 $bottom$ （ $top \le bottom < R$ ）：
将第 $bottom$ 行的元素累加到 $col\_sum$ 中（ $col\_sum[k] += M[bottom][k]$ ）； -
对 $col\_sum$ 应用Kadane算法，求得当前行区间内的最大子矩阵和；
-
更新全局最大值，遍历所有行区间后得到最终结果。
数学正确性证明
符号定义
设子矩阵的行范围为 $[top, bottom]$ ，列范围为 $[left, right]$ ，其和为：
Sum = \sum_{i=top}^{bottom} \sum_{j=left}^{right} M[i][j]交换求和顺序
将“先加行、再加列”的顺序交换为“先加列、再加行”：
Sum = \sum_{j=left}^{right} \left( \sum_{i=top}^{bottom} M[i][j] \right)令列和数组
col\_sum[j] = \sum_{i=top}^{bottom} M[i][j]，代入得：
Sum = \sum_{j=left}^{right} col\_sum[j]由此可证：固定行范围 $[top, bottom]$ 时，子矩阵的和等价于 $col\_sum$ 数组的连续子数组和。
覆盖所有子矩阵
由于任意子矩阵都对应唯一的连续行范围 $[top, bottom]$ ，枚举所有行区间可覆盖全部子矩阵。结合Kadane算法的正确性，遍历所有行区间后得到的最大值即为全局最优解。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[55][55];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
int ans = -100000;
for (int i = 0; i < n; ++i) {
vector<int> col(m);
for (int j = i; j < n; ++j) {
int ans2 = -100000;
int cursum = 0;
for (int k = 0; k < m; ++k) {
col[k] += a[j][k];
cursum = max(cursum + col[k], col[k]);
ans2 = max(ans2, cursum);
}
ans = max(ans, ans2);
}
}
cout << ans << endl;
}
int main() {
int t = 1;
while (t--) solve();
return 0;
}复杂度分析
-
一维问题：时间复杂度 $O(n)$ ，仅需一次遍历数组；空间复杂度 $O(1)$ （优化后无需存储完整 $dp$ 数组或前缀和数组）。
-
二维问题：时间复杂度 $O(R^2C)$ ，其中 $R$ 为行数、 $C$ 为列数；空间复杂度 $O(C)$ ，用于存储列和数组。
总结
Kadane算法的核心在于通过动态规划定义“以当前元素结尾的最大子段和”，将问题拆解为递推子问题。本文通过严谨的数学推导，补充证明了Kadane算法与“前缀和+维护最小值”方法的完全等价性，揭示了其增量视角背后的全局数学本质。通过降维思想，该算法可从一维扩展至二维，解决最大子矩阵和问题。其高效的时间复杂度与严谨的数学基础，使其成为解决连续子段和问题的经典算法。