一、问题介绍

给定一个数组a[n],求数组a的连续元素的子数组的和的最大值。

二、问题分析

根据题目意思,将抽象的描述化为具体:假设给定的数组为a[n],n=7,数组元素为{2,3,-22,5,11,-8,88},根据题意, 最后的结果应该为b[m] = {5,11,-8,88},sum(b) = 96。那么,根据这个意思,很快我们就可以想到一个算法: 用三个指针i,j,k(注意这里的指针不是程序语言中的指针,这里可以理解为一个在数组上滑动的游标)。我们让i 指向数组第一个元素,j指向i循环到n,k指向i循环到j,i遍历一遍数组。这样i=[0,n),j=[i,n),k=[i,j]。 其中k区间就是任意连续元素的数组,这样就可以求出每一个子数组的和。当i=0时候:求子数组{2}的和,子数组{2,3}的和…;当i=1时候:求子数组{3}的和,{3,-22} 的和,……然后根据所有子数组求出最大值就是了。代码如下:

int getSumOne(int a[],int len){
    int i,j,k;
    int maxsum = a[0];
    for(i = 0;i < len;i++){
        for(j = i;j < len;j++){
            int sum = 0;
            for(k = i;k <= j;k++){
                sum += a[k];
            }//子数组和
            if(sum > maxsum){
                maxsum = sum;
            }
        }
    }
    return maxsum;
}

上面的程序时间复杂度为O(n^3),确实有点复杂呀,其实稍微思考下,就会发现,上述程序我们是通过不断 比较最大值maxsum和当前子数组的和sum,将大的赋给maxsum。其实,当求子数组[i,j]的和的最大值,就是 求max{[i,j-1],[i,j]},因此没必要每次都丢弃上一个子数组的sum,比如子数组sum({2})=2,则sum({2,3})= sum({2})+a[1] = 5,虽然当子数组扩展的时候,可能有负数元素,但是maxsum中保存的始终是最大值。所以代码修改为:

int getSumTwo(int a[],int len){
    int i,j;
    int maxsum = a[0];
    for(i = 0;i < len;i++){
        int sum = 0;
        for(j = i;j < len;j++){
            sum += a[j];
            if(sum > maxsum){
                maxsum = sum;
            }
        }
    }
    return maxsum;
}

通过这样的变化,时间复杂度降低到了O(n^2)了。但是,还是有点复杂,所以要继续想办法。这次改用分治的思想, 将解决规模为n的问题,递归解决两个规模近似n/2的子问题,然后合并结果。大概的思路就是,将问题n的向量 分解为大小差不多的两个子向量a,b,然后子向量再分解,以此递归求解。对于每次a,b的求解,其实最大子向量 要么在a中,要么在b中,或者在跨域a,b之间的向量。然后最后取得最大的解就是所求的解了。看代码:

//O(nlog(n))
int getSumThree(int a[],int start,int end){
    int i,m;
    int sum=0,maxsum1,maxsum2;
    int maxsum=0;
    int lsum = 0,rsum = 0;

    if(start > end){
        return 0;
    }
    if(start == end){
       return a[start];
    }
    m = start + (end - start) / 2;
    maxsum1 = a[m],sum = 0;
    for(i = m;i >= start;i--){
        sum += a[i];
        if(sum > maxsum1){
           maxsum1 = sum;
        }

    }
    maxsum2 = a[m + 1], sum = 0;
    for(i = m + 1;i <= end;i++){
        sum += a[i];
        if(sum > maxsum2){
            maxsum2 = sum;
        }
    }
    maxsum = maxsum1 + maxsum2;

    lsum = getSumThree(a,start,m);

    if(maxsum < lsum){
        maxsum = lsum;
    }
    rsum = getSumThree(a,m+1,end);

    if(maxsum < rsum){
        maxsum = rsum;
    }
    return maxsum;
}

好家伙,代码相比之前的多了不少,但这是最好了吗?答案是否定的,因为还有更好的,而且代码量也比上面的 少,真是万幸啊。最后,可以达到O(n)的时间复杂度,思路也是很简单的,我们只需要扫描一遍数组,然后每次将 最大的累加和sum与所求出的最大和maxsum比较,如果大了,则替换最大和。当遇到sum累计和为负数时,就丢弃前面的累计和变量sum。 如果当前元素大于sum,则将该数赋值给sum,继续扫描累加求maxsum。如下代码:

int getSumFour(int a[],int len){
   int i;
   int maxsum = a[0];
   int sum = a[0];
   for(i = 1;i < len;i++){

       sum += a[i];
       if(sum < 0){
            if(a[i] > sum){
                sum = a[i];
            }

       }
       if(sum > maxsum){
            maxsum = sum;

       }

   }
    return maxsum;
}

总结

简单总结了下求最大子数组和的方法。

##文档信息