Kadane算法

Kadane算法——最大子数组和问题

问题定义
给定一个整数数组，找出其中和最大的连续子数组，并返回这个最大和。
子数组：数组中连续的元素序列。例如数组 [1,2,3,4] 的子数组有 [1]、[1,2]、[2,3]、[1,2,3] 等。
Kadane算法的核心思想
Kadane算法基于动态规划的思想，通过一次遍历就能找到最大子数组和。
核心状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])

其中 dp[i] 表示以第i个元素结尾的最大子数组和。

算法步骤：

1. 维护两个变量：current_max（当前最大值）和 global_max（全局最大值）
2. 从第二个元素开始遍历数组
3. 对于每个元素，选择较大值：要么单独成为新的子数组开始，要么加入前面的子数组
4. 更新全局最大值

算法示例

以数组 [5, -3, 2, -1, 4] 为例：
初始：current_max = 5, global_max = 5

i=1, nums[1]=-3:
  current_max = max(-3, 5+(-3)) = max(-3, 2) = 2
  global_max = max(5, 2) = 5

i=2, nums[2]=2:
  current_max = max(2, 2+2) = 4
  global_max = max(5, 4) = 5

i=3, nums[3]=-1:
  current_max = max(-1, 4+(-1)) = 3
  global_max = max(5, 3) = 5

i=4, nums[4]=4:
  current_max = max(4, 3+4) = 7
  global_max = max(5, 7) = 7

最终答案：7，对应子数组 [2, -1, 4]

为什么这样做是对的？

当 current_max + nums[i] < nums[i] 时，说明前面的子数组对当前元素产生了"负贡献"，此时应该抛弃前面的结果，从当前元素重新开始。这样保证了每一步都选择局部最优解，最终得到全局最优解。
完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Result {
    long long max_sum;
    int start;
    int end;
};

Result kadane(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {0, -1, -1};
    
    long long current_max = nums[0];
    long long global_max = nums[0];
    int start = 0, end = 0, temp_start = 0;
    
    for (int i = 1; i < n; i++) {
        if (nums[i] > current_max + nums[i]) {
            current_max = nums[i];
            temp_start = i;  // 新的候选起点
        } else {
            current_max += nums[i];
        }
        
        if (current_max > global_max) {
            global_max = current_max;
            start = temp_start;
            end = i;
        }
    }
    
    return {global_max, start, end};
}

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    Result result = kadane(nums);
    cout << "最大子数组和: " << result.max_sum << endl;
    cout << "子数组范围: [" << result.start << ", " << result.end << "]" << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n)，只需要一次遍历
• 空间复杂度：O(1)，只使用了常数个额外变量

特殊情况处理

1. 全为负数：返回最大的那个负数
2. 空数组：根据题目要求返回0或报错
3. 数据范围大：使用 long long 防止溢出

推荐练习题

• LeetCode 53: Maximum Subarray
• LeetCode 918: Maximum Sum Circular Subarray
• 杭电OJ 1003: Max Sum

算法扩展

• 二维数组的最大子矩阵和
• 环形数组的最大子数组和
• 找出所有最大和的子数组

Kadane算法是动态规划在数组问题中的经典应用，掌握其思想对解决类似问题很有帮助。