C++语言编程 最大子段和

Question

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0。要求算法的时间复杂度为O(n)。

输入格式:
输入有两行： 第一行是n值（1<=n<=10000)； 第二行是n个整数。

输出格式:
输出最大子段和。

输入样例:
在这里给出一组输入。例如：

6
-2 11 -4 13 -5 -2
输出样例:
在这里给出相应的输出。例如：

20

#include
using namespace std ; ………………
………………………………

Answer 1

 也可以用DP

#include <stdlib.h>

#include<stdio.h>

int main()

{

    int count;

    int a[100];

    int b[100];

    int i;

    int max;

    scanf("%d",&count);

    for(i=0; i<count; i++)

    {

        scanf("%d",&a[i]);

    }

    b[0]=a[0];

    max=b[0];

    for(i=1; i<count; i++)

    {

        if(b[i-1]>0)

            b[i]=b[i-1]+a[i];

        else

            b[i]=a[i];

        if(b[i]>max)

            max=b[i];

    }

    printf("%d\n",max);

    return 0;
}

Answer 2

 #include <cstdio>

typedef long long LL;

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    LL t, tmp;
    LL ans = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%lld", &t);
        if(i > 0 && tmp > 0)
            t += tmp;
        if(ans < t)
            ans = t;
        tmp = t;
    }   
    printf("%lld\n", ans);
    return 0;
}

Answer 3

dp做法

#include <bits/stdc++.h>
using namespace std;

int args[1005];//数据范围自己取
int dp[1005];

int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> args[i];
    }
    dp[1] = args[1];
    int maxn = -1e9;
    for(int i = 2;i <= n;i++)
    {
        dp[i] = max(dp[i - 1] + args[i],args[i]);
        maxn = max(maxn,dp[i]);
    }
    cout << maxn << endl;
    return 0;
}