输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。

输入描述:

【重要】第一行为数组的长度N（N>=1）

 接下来N行，每行一个数，代表数组的N个元素

输出描述:

最大和的结果

因为水平问题，最先想到的想法当然是穷举，两层循环，但是这样的话时间复杂度就是O(n^2)!
下面展示一下吧：

#include <stdio.h>

#define N 1000

int main(){

    int array[N];

    int temp[N];

    int n,i,sum=0,j,max,maxx;

    scanf("%d", &n);

    for(i=0;i<n;i++){

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

    }

    maxx=max=array[0];

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

    {

        for(j=i;j<n;j++)

        {

            sum+=array[j];

            if(sum>=max)

            {

                max=sum;

            }

        }

        temp[i]=max;

        max=sum=0;

    }

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

    {

        if(maxx<=temp[i])

        {

         maxx=temp[i];   

        }

    }

    printf("%d",maxx);

    return 0;

}

例如以上，本题如果没有好好读题的话很容易就会跳入出题者的坑里面去，就容易使用穷举法，计算出每一个方法，但是这样的话，时间复杂度就是O(n^2),不符合题意。！
下面展示AC过的代码：

#include <stdio.h>

#define N 1000

int main(){

    intarray[N];

    intn,i,sum=0,max;

    scanf("%d",&n);

    for(i=0;i<n;i++){

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

    }

    max=array[0];

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

    {

        sum+=array[i];

        if(max<sum)

            max=sum;

        if(sum<0)

            sum=0;

    }

    printf("%d",max);

    return0;

}