题解 | #最大序列和# 使用Kadane算法求最大序列和

Kadane算法是一种非常适合用来求最大序列和的算法，其核心思想就是判断当前的序列和与当前元素之间的大小关系：

• 如果是序列和大，则存储当前序列和；
• 若当前元素大，则认为取当前元素即为最大，将当前序列和设为当前元素的值；

如此遍历完所有元素即可获得最大元素和，Kadane算法的时间复杂度为 O(n)。

C语言实现代码如下：

#include <stdio.h>

long long get_max_seq_sum(long long *seq, int n) {
    long long cur_sum = seq[0];
    long long max_sum = seq[0];
    for (int i=1; i<n; ++i) {
        cur_sum = (seq[i] > cur_sum + seq[i]) ? seq[i] : (seq[i] + cur_sum);
        max_sum = max_sum > cur_sum ? max_sum : cur_sum; 
    }
    return max_sum;
}

int main() {
    int a;
    long long seq[1000000];
    while (scanf("%d", &a) != EOF) { // 注意 while 处理多个 case
        // 64 位输出请用 printf("%lld") to 
        for (int i=0; i<a; ++i) {
            scanf("%lld", &seq[i]);
        }
        printf("%lld\n", get_max_seq_sum(seq, a));
    }
    return 0;
}