一个二维数组搞定最大子矩阵

解题思路:

1.设一个足够大的二维数组

2.从[1][1]开始向右下累加，使每个位置表示其左上方（包括该位置本身的数）的和

3.四重for循环（前两重与后两重代表两个指针，指示矩阵的左上角和右下角）

4.利用累加好的数组减去矩阵外的数的总和
5.逐个比较得到最大值
注意事项:
*最关键一步在于得到每个子矩阵的具体大小，在减去子矩阵外的总值时，分别减去sum[i-1][t]和sum[k][j-1]位置的值，

但其中已包含了两遍sum[i-1][j-1]位置的值（即该两数值重合累加的部分），因此要加回一次sum[i-1][j-1]，这是关键！

参考代码:

#include

using namespace std;

int N,a[105][105],sum[105][105];

int main()

{

    cin>>N;

    for(int i=1;i<=N;i++)

    {

        for(int j=1;j<=N;j++)

        {

             cin>>sum[i][j];

        }

    }

    for(int i=1;i<=N;i++)

   {

        for(int j=1;j<=N;j++)

        {

             sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];

        }

   }

    int a,b,c,d;

int maxi=-999999;

for(int i=1;i<=N;i++)

{

for(int j=1;j<=N;j++)

{

for(int k=i;k<=N;k++)

{

for(int t=j;t<=N;t++)

{

//maxi=max(maxi,sum[k][t]-sum[i-1][t]-sum[k][j-1]+sum[i-1][j-1]);

if(maxi<sum[k][t]-sum[i-1][t]-sum[k][j-1]+sum[i-1][j-1])

    {

        maxi=sum[k][t]-sum[i-1][t]-sum[k][j-1]+sum[i-1][j-1];

        a=i,b=j,c=k,d=t;

    }

}

}

}

}

cout<<maxi;

// cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;

return 0; 

}