本题的三种思路：

方法一：枚举法

我们先来看一下，二维数组

可以展开编程一维数组 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 我们只要找出来这个子数组元素之和最大即可，利用穷举法如下

for(i=0;i<n;i++)
{
    for(j=0;j<=i;j++)
    {
        sum = 0;
        for(k=j;k<=i;k++)
            sum += a[k];
        if(sum > max)    max = sum;
    }
}

方法二：前缀和优化

record[0] = 0; for(i=1;i<=n;i++) //用下标1~n来储存n个数 record[i] = record[i-1] + a[i]; //用record记录a[i]前i个的和

max = 0;
for(i=1;i<=n;i++)
{
    for(j=0;j<i;j++)
    {
        sum = record[i] - record[j];//这里注意j是从0开始的
        if(sum > max)    max = sum;
    }
}

方法三：动态规划

若想找到n个数的最大子段和，那么要找到n-1个数的最大子段和，这就出来了。我们用b[i]来表示a[0]...a[i]的最大子段和，b[i]无非有两种情况 ： (1)最大子段一直连续到a[i] 　 (2)以a[i]为首的新的子段　。 由此我们可以得到b[i]的状态转移方程：b[i]=max{b[i-1]+a[i],a[i]}。最终我们得到的最大子段和为max{b[i], 0<=i<n}

int MaxSubArray(int a[],int n)
{
    int i,b = 0,sum = 0;
    for(i = 0;i < n;i++)
    {
        if(b>0)                // 若a[i]+b[i-1]会减小
            b += a[i];        // 则以a[i]为首另起一个子段
        else
            b = a[i];
        if(b > sum)
            sum = b;
    }
    return sum;
}

上面是一维的动态规划，二维的思路就是一维的扩展 我们假设所求N*N的矩阵的最大子矩阵是从i列到j列，q行到p行，如下图所示（假设下标从1开始）

最大子矩阵就是图示红色部分，如果把最大子矩阵同列的加起来，我们可以得到一个一维数组{a[q][i]+······+a[p][i] , ······ ，a[q][j]+······+a[p][j]} ，现在我们可以看出，这其实就是一个一维数组的最大子段问题。如果把二维数组看成是纵向的一维数组和横向的一维数组，即可求出题解