【软件工程】代码复审与子数组最大和线性算法寻找问题

时间：2014-03-10 21:56:42 阅读：507 评论：0 收藏：0 [点我收藏+]

小组成员：刘铸辉何晓楠

1.子数组最大和线性算法

　　题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

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

　　如果没有O(n)这条要求，那么我们可以通过枚举法，枚举出所有的子数组，然后分别对每个子数组求和，这个规模将达到O(n³).

　　在课堂上我和铸辉就用了这样的算法。

int zuida(const int A[],int N)    
{    
    int ThisSum=0 ,MaxSum=0,i,j,k;    
    for(i=0;i<N;i++)    
        for(j=i;j<N;j++)    
        {    
            ThisSum=0;    
            for(k=i;k<j;k++)    
                ThisSum+=A[k];    
                
            if(ThisSum>MaxSum)    
                MaxSum=ThisSum;    
        }    
        return MaxSum;    
}

结果虽然是对的，但是并没有达到老师的要求，课下通过查资料和学习，练习了网上的一些经典的算法以后，理清了O（n）算法的基本思想

　　O(n)算法的基本思想是依次扫描数组中所有的数，用一个变量sum来保存当前所有子数组和中最大的那个值，用另外一个变量b记录扫描到第i个数的时候，所有子数组的最大值，一旦发现b的值为负数，则将之前的子数组全部抛弃，所以b置为0，直到b的值大于sum的值才更新b为sum的值，当整个数组扫描完毕的时候，所有子数组的最大值也就算出来了。

　　以下是我们的算法及实现结果。

#include<stdio.h><br>#include<string.h><br>#define N 10
int zuida(int 
a[N])
{
    int 
sum=0;
    int 
m=0;
    int 
i;
    int 
b=0;
    for(i=0;i<N;i++)
    {
        if(b<0)
            b=a[i];
        else
            b=b+a[i];
        if(sum<b)
            sum=b;
    }
    return 
sum;
}
 
void 
main()
{
    int 
a[N]={2,-3,-25,20,13,-5,18,20,-7,-12};
    printf("最大子数组的和为%5d\n",zuida(a));
}