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