子数组的最大和[算法]

               

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的

和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

 

       这个题我的第一感觉就是3层for循环直接进行么，就喜欢暴力for循环，遍历所有可能，还是自己的想法太low

了，其实这个题的时间复杂的度可以变为o(n),下面的代码分别用3个不一样的时间复杂度完成的题，所以代码敲完要 优化，也要问一下其他，自己的代码不一定很棒棒哒。废话也就不多说了，因为这个算法比较简单，所以不多做解释了。

 

1 时间复杂度为o(n^3)

#include <stdio.h> 
#include<stdlib.h>
int main(){
int n,t;
int *a;
int i,j;
int x=0,y=0,m;
int max=0,sum=0;
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
  scanf("%d",a+i);
for(i=0;i<n;i++)    
    {
       for(j=0;j<n;j++)
       {
         m=j;
         sum=0;
     for(int k=0;k<i;k++)
       sum+=a[m++];
  if(max<sum)
    {
     max=sum;
     x=i;
     y=j;     
    }     
       }

}
printf("x=%d,y=%d\n",x,y);
if(x>y){t=x;x=y;y=t;}      //如果x>y  ，就进行交换 

for(i=x;i<=y+1;i++)        //这里+1，是因为数组虽然标记的数加+1才是实际的个数 
   printf("%d ",a[i]);
printf("\nmax=%d\n",max);
return 0;
} 

 

2 时间复杂度为o(n^2)

#include<stdio.h>
#include<stdlib.h>
int main()
{
int n;
int *a;
int i,j;
int sum=0,max=0;
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
  scanf("%d",a+i);
for(i=0;i<n;i++)
{
sum=0;      //  sum每次置0 
  for(j=i;j<n;j++)
  {
     sum+=a[j];
     if(max<sum)
        max=sum;

  }
}
 printf("max=%d\n",max); 
return 0;
} 

 

 

时间复杂度为o(n)

#include<stdio.h>
#include<stdlib.h>
int main()
{
int n;
int *a;
int i;
int sum=0,bettersum=0;
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
  scanf("%d",a+i);
    for(i=0;i<n;i++){
           sum+=a[i];
           //如果当前和值为零，则把当前和值置为零 
   if(sum<0)
      sum=0;
//如果当前和值大于最优值，则最优值记录当前和值 
   if(bettersum<sum)
      bettersum=sum;    

    }
    //如果数组全为负值，只需要找到一个最大的负值 
if(0==bettersum) {
bettersum=a[0];
for(i=0;i<n;i++){
if(a[i]>bettersum)
  bettersum=a[i];
}
}

    printf("bettersum=%d\n",bettersum);
return 0;
}