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#includeusing 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;
}