OJ_最大序列和

题干

C++实现

#include <stdio.h>
#include <algorithm>
using namespace std;

long long s[1000001];
long long dp[1000002];//dp[i]是前i个元素中必须包含右边缘的最大子序和

int main() {
    int n;
    scanf("%d",&n);
    for(int i = 0; i< n;i++){
        scanf("%lld",&s[i]);
    }

    dp[1] = s[0];
    long long curmax = dp[1];
    for(int i = 2;i<=n;i++){
        if(dp[i-1] <= 0){
            dp[i] = s[i-1];
        }else{
            dp[i] = s[i-1]+dp[i-1];
        }
        curmax = max(dp[i],curmax);
    }
    printf("%lld",curmax);
    return 0;
}
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