51NOD 1049 最大子段和

Description

N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

Input

第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）

Output

输出最大子段和。

Input示例

6

-2

11

-4

13

-5

-2

Output示例

20

分析：用一个值遍历所有数，再用一个值记录所有遍历后的最大数。
1

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
long long M(long long a, long long b) {return a>b?a:b;}

int main()
{
    long long n, x, sum = 0, summax = 0;
    scanf("%lld", &n);
    for(long long i=1; i<=n; i++)
    {
        scanf("%lld", &x);
        sum = M(sum, 0) + x;
        summax = M(sum, summax);
    }
    printf("%lld\n", summax);
    return 0;
}

2

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
    long long n, x, sum = 0, ans = 0;
    scanf("%lld", &n);
    for(long long i=1; i<=n; i++)
    {
        scanf("%lld", &x);
        sum += x;
        if(sum > ans)
            ans = sum;
        if(sum < 0)
            sum = 0;
    }
    printf("%lld\n", ans);
    return 0;
}

3 毕竟是动态规划，利用动规解一波（不太懂）（雾）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1E5 + 10;
int a[maxn];
ll dp[maxn];
int main()
{
        int n,flg = 1;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; ++i)
        {
            scanf("%d",&a[i]);
            if(a[i] >= 0)   flg = 0;
        }
        if(flg)
        {
                printf("0\n");return 0;
        }
        memset(dp,0,sizeof(dp));
        ll ans = 0;
        dp[0] = a[0];
        for(int i = 1 ; i < n ; ++i)
        {
                dp[i] = max((long long)a[i],dp[i - 1] + a[i]);
                ans = max(dp[i] , ans);
        }
        printf("%lld\n",ans);
        return 0;
}

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/54864276