21. 最大序列和

题目描述

给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。 对于S的所有非空连续子序列T，求最大的序列和。 变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,263-1）以内。

输入描述:

第一行为一个正整数N，第二行为N个整数，表示序列中的数。

输出描述:

输入可能包括多组数据，对于每一组输入数据，
仅输出一个数，表示最大序列和。

示例1

输入

5
1 5 -3 2 4

6
1 -2 3 4 -10 6

4
-3 -1 -2 -5

输出

9
7
-1

解法一

#include <stdio.h>
#include <limits.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int main() {
    for (int N; ~scanf("%d", &N);) {
        int sum = 0;
        int res = INT_MIN;    //int 最小值
        for (int x, i = 0; i < N; i++) {
            scanf("%d", &x);
            sum = max(sum + x, x);    //一开始就求序列和的最大值，如果前面序列和小于当前输入值，则放弃序列和，这样一路走下来总是最优的
            res = max(res, sum);    //保留最大的序列和
        }
        printf("%d", res);
    }
    return 0;
}

思路二：动态规划

本质上和上述方法一样，但是理解起来倾向于动态规划的思想，更直观。
记 dp[i] 为以第 i 个数结尾的最大序列和，则 dp[i] = max{dp[i - 1] + num[i], num[i]}，其中 num[i] 表示第 i 个数

解法二

#include <stdio.h>
#include <malloc.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int main() {
    for(int N; ~scanf("%d", &N);) {
        int res = 0;    //输出的结果
        int *dp = (int *) malloc (sizeof(int) * N);    //dp 数组
        int *num = (int *) malloc (sizeof(int) * N);    //输入的数组
        for (int i = 0; i < N; i++)
            scanf("%d", &num[i]);
        res = dp[0] = num[0];
        for (int i = 1; i < N; i++)
            dp[i] = max(dp[i - 1] + num[i], num[i]);
        for (int i = 1; i < N; i++)
            res = max(res, dp[i]);
        printf("%d", res);
        free(dp);
        free(num);
    }
    return 0;
}