给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的
和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i<n,j>=i,j<n，
例如  31 -41 59 26 -53 58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。

网上直接穷举法的程序如下,麻烦说明下标红色的作用                     
//直接穷举法,求出所有可能的组合和  O(N^3)   
int getSum1(int a[],int N)   
{   
    int max=-10000000;   
    for(int i=0;i<N;i++)   
    {   
        for(int j=i;j<N;j++)   
        {   
            int tmp=0;   
            for(int k=i;k<=j;k++)   
                tmp+=a[k];   
            if(tmp>max)   
                max=tmp;   
        }   
    }   
    return max;   
}   

下边是我所想的解法,麻烦帮忙看下行不行(简单验证是OK,不过不清楚是否有BUG)
int getSum1(int a[],int N)   
{   
    int max=-10000000;
    int tmp=0;  
    for(int i=0;i<N;i++)   
    {   
        tmp=0;
        for(int j=i;j<N;j++)   
        {   
            tmp+=a[j];   
            if(tmp>max)   
                max=tmp;   
        }   
    }   
    return max;   
}   

int getSum1(int a[],int N)   
{   
    int max=-10000000;   
    for(int i=0;i<N;i++)   
    {   
        for(int j=i;j<N;j++)   
        {   
            int tmp=0;   
            for(int k=i;k<=j;k++)   
                tmp+=a[k];   
            if(tmp>max)   
                max=tmp;   
        }   
    }   
    return max;   
}   
我来解释一下：因为要求的数组的长度是不确定的，而在原来的数组中却要是连续。
前面的两个for穷举了所有的可能，其中i为子数组的开始位置，j为结束位置，包含了所有的可能的数组长度和不同的元素集合。
而在红色部分的for中k从上面i，j确定的一个子数组中，从i(开始位置)开始到j（结束位置)，累加其中的元素的和，最后将和比较大小。
你自己写的程序是不对的。你程序中所求的子数组开始的位置可以是每个元素，而结束的位置，却始终是最后一个元素，也就是说你求的数组并不是所有的数组，并不能列举所有的情况。从上面的程序,还有其结果就可以看出你的程序是错误的。

[ 本帖最后由 qq1023569223 于 2011-2-28 07:24 编辑 ]

#include <stdio.h>

void foo( int buf[], int n )
{
    int a=0, b=0, sum=0; // a为起始下标，b为连续长度，sum为和
    int a1=0, b1=0, sum1=0; // 暂时的可能
    for( int i=0; i<n; ++i )
    {
        sum1 += buf[i]; // 接纳此元素后的和
        if( sum1 > 0 ) // 只要大于零，将来总是有可能变得更大的。有希望就要保留！
        {
            ++b1;
        }
        else // 负数将来也有可能变得更大呀？我靠，那我还不如直接从0开始
        {
            a1 = i+1;
            b1 = 0;
            sum1 = 0;
        }

        if( sum1 > sum ) // 如果“暂时的可能”最优，当然它就成“正式的”啦
        {
            a = a1;
            b = b1;
            sum = sum1;
        }
    }

    if( b != 0 )
        printf( "Sum(%d,%d)=%d ", a, a+b-1, sum );
    else
        printf( "%s ", "全TMD没个正数，当然是零个连续和最大呀！" );
}

int main()
{
    int buf[] = { 2,3,-6,3,4,3,-2,5,2,-3 }; // Sum(3,8)=15
    foo( buf, sizeof(buf)/sizeof(buf[0]) );

    return 0;
}

整个算法就像一个蠕虫，头部每次向前爬一格，如果总和大于0的话就一直爬；如果小于0，那把尾巴缩到头部，头部继续爬
上述就是一个遍历的过程，现在只要将这过程中的最大和记录下来就行了

你的程序是对的，而且更简洁。

下面解释说明一下我的说法：
当i=2，j=5的时候，
你的程序算出的是a[2]+a[3]+a[4]+a[5]
而正确的应该是a[2]，a[2]+a[3]，a[2]+a[3]+a[4]，a[2]+a[3]+a[4]+a[5] 这也就是红色程序的作用
但是你的程序分别在j=2,j=3,j=4的时候已经做出了分别a[2]，a[2]+a[3]，a[2]+a[3]+a[4]
所以  你的程序是对的而且更简洁。