7-5 maximal submatrix sum problem

7-5 Maximum submatrix sum problem

Maximum submatrix sum problem . Given m That's ok n The integer matrix of columns A, O matrix A A submatrix of , Maximize the sum of its elements .

Input format :
In the first row, enter the number of rows of the matrix m And number of columns n（1≤m≤100,1≤n≤100）, And then type m×n It's an integer .

Output format :
The first row outputs the sum of the elements of the maximum submatrix , The second row is the row number range and column number range of the sub matrix in the whole matrix .

sample input 1:

5 6
60 3 -65 -92 32 -70
-41 14 -38 54 2 29
69 88 54 -77 -46 -49
97 -32 44 29 60 64
49 -48 -96 59 -52 25

sample output 1:
Output the first line 321 Represents the sum of the elements of a submatrix , Output the second line 2 4 1 6 Indicates that the row number of the submatrix is from 2 To 4, Column ordinal from 1 To 6

321
2 4 1 6

Code ：

#include<stdio.h>
int dp[5050][5050];
int m,n,ans=-999999,temp,num;
int main(){
    
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
    
            scanf("%d",&num);
            dp[i][j]=dp[i-1][j]+num;// Record each [i,j] Sum of matrices 
        }
    int x1,x2,y1,y2;
    for(int i=1;i<=m;i++)// A cycle , Used to control the lower boundary of the submatrix 
        for(int j=1;j<=i;j++){
    // A two-tier cycle , Used to control the upper boundary of submatrix 
            temp=0;
            int yy=1;
            for(int k=1;k<=n;k++){
    // A three-level loop is used to control the right boundary of the submatrix 
                temp+=(dp[i][k]-dp[j-1][k]);
                if(temp>ans)// If the value is greater than the maximum value, update 
                {
    
                    ans=temp;
                    x2=i;
                    y2=k;
                    x1=j;
                    y1=yy;
                }
                if(temp<0)
                {
    
                    temp=0;
                    yy=k+1;
                }
            }
        }
    printf("%d\n",ans);
    printf("%d %d %d %d",x1,x2,y1,y2);
}

202206222101 3、 ... and