引言

Kadane算法是解决最大子数组和问题的经典动态规划算法，由计算机科学家Jay Kadane于1984年提出。该算法以极其简洁的代码实现了O(n)的最优时间复杂度，是动态规划空间优化的典范。

问题背景

最大子数组和问题

LeetCode 53: 给定一个整数数组，找到具有最大和的连续子数组，返回其最大和。

示例：

1
2
3
输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组 [4, -1, 2, 1] 的和最大，为 6

应用场景

  • 股票交易：找到最佳买卖时机的最大利润
  • 信号处理：在噪声中找到最强信号段
  • 生物信息学：DNA序列分析
  • 数据分析：找到业务指标的最佳表现时段

算法演变

方法1: 暴力枚举

枚举所有可能的子数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxSubArray(vector<int>& nums) {
    int maxSum = INT_MIN;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i; j < nums.size(); ++j) {
            int sum = 0;
            for (int k = i; k <= j; ++k) {
                sum += nums[k];
            }
            maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

时间复杂度：O(n³)
问题：三层循环，效率极低

方法2: 优化暴力

利用前缀和优化：

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(vector<int>& nums) {
    int maxSum = INT_MIN;
    for (int i = 0; i < nums.size(); ++i) {
        int sum = 0;
        for (int j = i; j < nums.size(); ++j) {
            sum += nums[j];  // 累加，避免重复计算
            maxSum = max(maxSum, sum);
        }
    }
    return maxSum;
}

时间复杂度：O(n²)
问题：仍然较慢

方法3: 分治算法

如之前在DivideAndConqer.cpp中实现：

1
2
3
4
int maxSubArray(vector<int>& nums) {
    // 分成左右两半，递归求解
    // 考虑跨越中点的情况
}

时间复杂度：O(n log n)
优势：比O(n²)快，适合理解分治思想

方法4: Kadane算法

最优解法：

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(vector<int>& nums) {
    int maxEndingHere = nums[0];
    int maxSoFar = nums[0];
    
    for (int i = 1; i < nums.size(); ++i) {
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

时间复杂度：O(n)
空间复杂度：O(1)
完美！

Kadane算法原理

核心思想

对于数组中的每个位置，我们只需要做一个决定：

当前元素应该加入之前的子数组，还是从当前元素重新开始？

1
2
3
4
对于位置 i：
maxEndingHere[i] = max(nums[i], maxEndingHere[i-1] + nums[i])
                   ↑           ↑
                重新开始    加入之前的子数组

状态定义

  • maxEndingHere：以当前位置结尾的最大子数组和
  • maxSoFar：全局最大子数组和

决策过程可视化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
数组：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

位置0: maxEndingHere = -2, maxSoFar = -2
       [-2]

位置1: maxEndingHere = max(1, -2+1) = 1 (重新开始)
       maxSoFar = 1
       [1]

位置2: maxEndingHere = max(-3, 1-3) = -2 (继续)
       maxSoFar = 1
       [1, -3]

位置3: maxEndingHere = max(4, -2+4) = 4 (重新开始)
       maxSoFar = 4
       [4]

位置4: maxEndingHere = max(-1, 4-1) = 3 (继续)
       maxSoFar = 4
       [4, -1]

位置5: maxEndingHere = max(2, 3+2) = 5 (继续)
       maxSoFar = 5
       [4, -1, 2]

位置6: maxEndingHere = max(1, 5+1) = 6 (继续)
       maxSoFar = 6
       [4, -1, 2, 1] ← 答案！

位置7: maxEndingHere = max(-5, 6-5) = 1 (继续)
       maxSoFar = 6

位置8: maxEndingHere = max(4, 1+4) = 5 (继续)
       maxSoFar = 6
graph LR
    A[-2] -->|重新开始| B[1]
    B -->|继续| C[-3]
    C -->|重新开始| D[4]
    D -->|继续| E[-1]
    E -->|继续| F[2]
    F -->|继续| G[1]
    G -->|继续| H[-5]
    H -->|继续| I[4]
    
    style D fill:#FFE4B5
    style E fill:#FFE4B5
    style F fill:#FFE4B5
    style G fill:#90EE90

为什么这样做是对的？

关键洞察：

如果 maxEndingHere[i-1] < 0，那么加上它只会让结果变小，不如重新开始！

1
2
3
4
5
如果前面的和是负数：
  -5 + 3 = -2  (不如直接从3开始)
  
如果前面的和是正数：
  5 + 3 = 8   (应该继续)

代码实现

基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxSubArray(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int maxEndingHere = nums[0];  // 以当前位置结尾的最大和
    int maxSoFar = nums[0];       // 全局最大和
    
    for (int i = 1; i < nums.size(); ++i) {
        // 核心决策
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

动态规划视角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 等价的DP写法（更占空间）
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);  // dp[i] = 以i结尾的最大子数组和
    
    dp[0] = nums[0];
    int maxSum = dp[0];
    
    for (int i = 1; i < n; ++i) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }
    
    return maxSum;
}

观察：dp[i]只依赖于dp[i-1]，所以可以用一个变量代替数组！

返回子数组位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct SubarrayInfo {
    int sum;
    int start;
    int end;
};

SubarrayInfo maxSubArrayWithIndices(vector<int>& nums) {
    int maxEndingHere = nums[0];
    int maxSoFar = nums[0];
    int start = 0, end = 0;
    int tempStart = 0;
    
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > maxEndingHere + nums[i]) {
            maxEndingHere = nums[i];
            tempStart = i;  // 重新开始，更新起始位置
        } else {
            maxEndingHere = maxEndingHere + nums[i];
        }
        
        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            start = tempStart;
            end = i;
        }
    }
    
    return {maxSoFar, start, end};
}

正确性证明

归纳法证明

基础情况：一个元素时，算法显然正确。

归纳假设：假设对于前i-1个元素，算法正确。

归纳步骤：对于第i个元素：

  1. 如果maxEndingHere[i-1] + nums[i] > nums[i]

    • 说明前面的子数组对当前有贡献
    • 应该继续

  2. 如果maxEndingHere[i-1] + nums[i] <= nums[i]

    • 说明前面的子数组拖后腿
    • 应该重新开始

因此，算法在每一步都做出了最优决策。

反例分析

错误想法：遇到负数就重新开始？

1
2
3
数组：[5, -2, 3]
错误：遇到-2就重新开始 → 最大和 = 5
正确：5 + (-2) + 3 = 6

Kadane的优势：它考虑的是"累积贡献"，而不是单个元素的正负。

变种问题

1. 环形数组的最大子数组和

LeetCode 918: 环形子数组的最大和

思路：环形数组的最大子数组只有两种情况：

  1. 不跨越边界：正常Kadane算法
  2. 跨越边界：总和 - 最小子数组和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxSubarraySumCircular(vector<int>& nums) {
    int totalSum = 0;
    int maxSum = INT_MIN, minSum = INT_MAX;
    int maxEndingHere = 0, minEndingHere = 0;
    
    for (int num : nums) {
        totalSum += num;
        
        // 最大子数组
        maxEndingHere = max(num, maxEndingHere + num);
        maxSum = max(maxSum, maxEndingHere);
        
        // 最小子数组
        minEndingHere = min(num, minEndingHere + num);
        minSum = min(minSum, minEndingHere);
    }
    
    // 特殊情况：所有元素都是负数
    if (maxSum < 0) return maxSum;
    
    return max(maxSum, totalSum - minSum);
}

可视化：

1
2
3
4
5
6
数组：[5, -3, 5]

情况1 (不跨越)：[5, -3, 5] → 和 = 7
情况2 (跨越)：[5] + [5] → 和 = 10 ✓

计算：总和 - 最小子数组和 = 7 - (-3) = 10

2. 乘积最大子数组

LeetCode 152: 乘积最大子数组

关键：负数 × 负数 = 正数，需要同时维护最大值和最小值！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxProduct(vector<int>& nums) {
    int maxEndingHere = nums[0];
    int minEndingHere = nums[0];
    int result = nums[0];
    
    for (int i = 1; i < nums.size(); ++i) {
        int num = nums[i];
        int tempMax = maxEndingHere;
        
        // 可能：当前元素、最大值×当前、最小值×当前
        maxEndingHere = max({num, maxEndingHere * num, minEndingHere * num});
        minEndingHere = min({num, tempMax * num, minEndingHere * num});
        
        result = max(result, maxEndingHere);
    }
    
    return result;
}

示例：

1
2
3
4
5
6
7
8
数组：[2, 3, -2, 4]

i=0: max=2,  min=2,  result=2
i=1: max=6,  min=3,  result=6   (2×3)
i=2: max=-2, min=-12, result=6  (6×-2 vs 3×-2)
i=3: max=4,  min=-48, result=6  (-12×-2 才是最大的中间结果，但4最后才来)

答案[2,3]的乘积=6

3. 股票买卖最佳时机

LeetCode 121: 买卖股票的最佳时机

转换：最大利润 = 最大子数组和（差分数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices) {
    if (prices.size() < 2) return 0;
    
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for (int i = 1; i < prices.size(); ++i) {
        maxProfit = max(maxProfit, prices[i] - minPrice);
        minPrice = min(minPrice, prices[i]);
    }
    
    return maxProfit;
}

Kadane视角：

1
2
3
4
5
6
// 将价格数组转换为差分数组
vector<int> diff;
for (int i = 1; i < prices.size(); ++i) {
    diff.push_back(prices[i] - prices[i-1]);
}
// 然后在diff上运行Kadane算法

性能对比

时间复杂度对比

方法 时间复杂度 空间复杂度
暴力枚举 O(n³) O(1)
优化暴力 O(n²) O(1)
分治算法 O(n log n) O(log n)
Kadane算法 O(n) O(1)

为什么Kadane最优？

  1. 单次遍历：只需要扫描数组一次
  2. 常数空间：只用两个变量
  3. 无递归：没有函数调用开销
  4. 缓存友好：顺序访问，利用CPU缓存

总结

核心要点

  1. Kadane算法是最大子数组和的最优解
  2. 时间O(n)，空间O(1)
  3. 动态规划的空间优化经典例子
  4. 关键在于理解"何时重新开始"

算法模板

1
2
3
4
5
6
7
8
9
10
11
int kadane(vector<int>& nums) {
    int maxEndingHere = nums[0];
    int maxSoFar = nums[0];
    
    for (int i = 1; i < nums.size(); ++i) {
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

记忆口诀

加入或重启，两者取大；
全局最优，随时更新。

扩展学习

相关算法：

  • 最大子矩阵和：二维Kadane
  • 最长递增子序列：类似的DP思想
  • 股票买卖系列：状态机DP

推荐练习：