最大子段和

思路

经典中的经典——最大子段和，也叫最大子数组和。给你一个整数数组，找一段连续的子数组，使得它的元素之和最大。

最暴力的做法当然是枚举所有子数组，算出每个的和取最大值，但那是 的，数据大了就扛不住。

这里用的是 Kadane 算法，核心思想特别简单：我们维护一个变量 cur 表示"以当前元素结尾的最大子段和"。每读入一个新元素，就把它加到 cur 上，然后用 cur 去更新全局答案。如果 cur 变成负数了呢？那说明前面这一段已经是累赘了，不如从下一个元素重新开始，所以把 cur 归零。

为什么这样是对的？因为一个负数的前缀只会拖累后面的元素，丢掉它一定不亏。而只要 cur 还是正的，往后延伸就有可能拿到更大的和，所以我们贪心地继续累加。

注意一个细节：maxSum 的初始值要设得足够小（比如 LLONG_MIN），因为数组可能全是负数，这时答案就是最大的那个负数，而不是 0。

代码

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

int main() {
    int n;
    scanf("%d", &n);
    long long maxSum = -1e18, cur = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        scanf("%lld", &x);
        cur += x;                       // 把当前元素加入子段
        maxSum = max(maxSum, cur);       // 更新全局最大值
        if (cur < 0) cur = 0;           // 前缀和为负，果断丢弃
    }
    printf("%lld\n", maxSum);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long maxSum = Long.MIN_VALUE, cur = 0;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            cur += x;                           // 把当前元素加入子段
            maxSum = Math.max(maxSum, cur);      // 更新全局最大值
            if (cur < 0) cur = 0;               // 前缀和为负，果断丢弃
        }
        System.out.println(maxSum);
    }
}

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_sum = float('-inf')
    cur = 0
    for x in a:
        cur += x
        if cur > max_sum:
            max_sum = cur
        if cur < 0:
            cur = 0
    print(max_sum)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let maxSum = -Infinity, cur = 0;
    for (let i = 0; i < n; i++) {
        cur += a[i];
        if (cur > maxSum) maxSum = cur;
        if (cur < 0) cur = 0;
    }
    console.log(maxSum);
});

复杂度分析

  • 时间复杂度: ，只需要遍历数组一遍。
  • 空间复杂度: ，只用了两个额外变量，甚至不需要把数组存下来。

小结

Kadane 算法是动态规划和贪心思想的完美融合。本质上 cur 就是 dp 状态——以当前元素结尾的最大子段和，转移方程是 dp[i] = max(dp[i-1] + a[i], a[i])，而 cur < 0 时归零就等价于选择"从当前元素重新开始"。整个过程一遍扫描、常数空间，是面试和竞赛中出现频率极高的经典题目。