Advertisement
STANAANDREY

submatrix sum max

Aug 29th, 2019
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[51][51],s[51][51];
  4.  
  5. int main()
  6. {
  7.  
  8.     int n,m,i,j,maxi=-32000;
  9.     cin>>n>>m;
  10.     for (i=1; i<=n; i++)
  11.         for (j=1; j<=m; j++)
  12.             cin>>a[i][j];
  13.     for (i=1; i<=n; i++)
  14.         for (j=1; j<=m; j++)
  15.             s[i][j]=a[i][j]+s[i][j-1]+s[i-1][j]-s[i-1][j-1];
  16.     int x1,x2,y1,y2;
  17.     for (x1=1; x1<=n; x1++)
  18.         for (y1=1; y1<=m; y1++)
  19.             for (x2=x1; x2<=n; x2++)
  20.                 for (y2=y1; y2<=m; y2++)
  21.                     if (maxi<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1])
  22.                         maxi=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
  23.  
  24.     cout<<maxi;
  25.     return 0;
  26. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement