最大子矩阵问题 我用的暴力做法 不知道哪里出问题了

Question

#include<stdio.h>
#include<algorithm>
using namespace std;
int s[1005];
int arr[1005][1005];
int sum(int e,int r,int x,int y){
    int count=0;
    for(int i=e;i<e+x;i++){
        for(int j=r;j<r+y;j++){
            count+=arr[i][j];    //求矩阵和 
        }
    }
    return count;//将矩阵和返回给数组 
}
int main()
{
    int m,n,x,y,a;
    scanf("%d",&a);
    while(a--){
        scanf("%d %d %d %d",&m,&n,&x,&y);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&arr[i][j]);
            }
        }
        int e=0,r=0,w=0;
        while(e+x-1!=m&&r+y-1!=n){
            s[w++]=sum(e,r,x,y);
            if(r+y-1!=m) r++;//判断横边界 
            else if(r+y-1==m&&e+x-1!=n){//判断纵边界 
                r=0,e++;
            }
        }
        sort(s,s+w);//排序找最大的矩阵和 
        printf("%d\n",s[w-1]);
    } 
    return 0;
}

Answer 1

你的s数组有可能溢出
不暴力的方法

#include<stdio.h>

int arr[1005][1005]={0};
//arr[i][j]表示矩阵前i行与前j列组成的子矩阵的和，此处不初始化对结果无影响 

int main(){
    int m,n,x,y,T,i,j,max,temp;
    scanf("%d",&T);
    while(T--){
        max=0;
        scanf("%d%d%d%d",&m,&n,&x,&y);
        for(i=1;i<=m;i++){
            for(j=1;j<=n;j++){
                scanf("%d",&arr[i][j]);
                arr[i][j]+=arr[i][j-1]; 
            }
            for(j=1;j<=n;j++){
                arr[i][j]+=arr[i-1][j];
            } 
        }
        for(i=0;i<m-x;i++){
            for(j=0;j<n-y;j++){
                temp=arr[i+x][j+y]+arr[i][j]-arr[i][j+y]-arr[i+x][y];
                if(max<temp)max=temp;
            }
        }
        printf("%d\n",max);
    } 
    return 0;
}