最大区间和C语言

要求：给定任意一个区间，求该区间中最大和的区间值

方法：以下为逐渐优化的过程

1、没有任何变化的一个一个区间去比较，时间复杂度为O(n2)

代码如下：

#include<stdio.h>
int main()
{
    int a[10]={1,-2,4,1,-3,5,2,-2,1,-2};
    int sum=0,max=0;
    int op=0;
    if(a[0]>0){
        max=a[0];
    }
    for(int i=0;i<10;i++){
            sum=0;
        for(int j=i;j<10;j++){
            sum+=a[j];
            op++;
            if(sum>max)
                max=sum;
        }
    }
    printf("%d----%d\n",max,op);
    return 0;
}

2、求出每项下标之前的和，用和减比较，时间复杂度为O(n2)

代码如下：

#include<stdio.h>
int main()
{
    int a[10]={1,-2,4,1,-3,5,2,-2,1,-2};
    int sum[10],max=0;
    int op=0;
    sum[0]=a[0];
    for(int i=1;i<10;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=0;i<10;i++){
        for(int j=i;j<10;j++){
                if(i==0){
                    if(sum[i]>max)max=sum[i];
                }
                else {
                    if(sum[j]-sum[i-1]>max)max=sum[j]-sum[i-1];
                }
                op++;
        }
    }
        printf("%d----%d\n",max,op);
    return 0;
}

3、将其看成逐个输入的列表，输入同时比较是否大于前几个和，时间复杂度为O(n)

代码如下：

#include<stdio.h>
int main()
{
    int a[10]={1,-2,4,1,-3,5,2,-2,1,-2};
    int sum=0,tail=0;
    int op=0;
    if(a[0]>0){
        sum=tail=a[0];
    }
    for(int i=1;i<10;i++){
       if(tail+a[i]>sum){
            sum=tail+a[i];
            tail+=a[i];
       }
        else
            if(tail+a[i]>0)
                tail+=a[i];
            else
                tail=0;
            op++;
            }
        printf("%d----%d\n",sum,op);
    return 0;
}