Maximum submatrix
Mar 6, 2021 at 5:18pm UTC
We have an A matrix with N rows and M columns. Find the maximum sum submatrix in the matrix.
The program will display the maximum amount of a submatrix on the screen
Restrictions:
1 ≤ N,M ≤ 50
-3 000 ≤ a[i][j] ≤ 3 000
Input :
4 4
-1 -1 -1 -1
-1 4 4 -1
-1 -1 -1 -1
-1 -1 -1 -1
Output : 8
Input:
4 4
-1 -1 -1 -55
-1 -54 -1 -1
-1 -99 -1 -1
-1 -1 -1 -1
Output : -1
The code only works for quadratic matrices, if I have::
Input :
2 3
1 2 3
1 2 3
Output: 6, but the correct answer is 12
I don't want another code, repair my code please.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
#include <bits/stdc++.h>
using namespace std;
int N, M, a[51][51], maxi, sp, v[51];
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) {
cin >> a[i][j];
a[i][j] += a[i - 1][j];
}
maxi = -1000000;
for (int i = 1; i <= N; i++)
for (int j = i; j <= M; j++) {
for (int k = 1; k <= N; k++)
v[k] = a[j][k] - a[i - 1][k];
int sp = 0;
for (int k = 1; k <= N; k++) {
sp += v[k];
if (sp > maxi) {
maxi = sp;
}
if (sp < 0) {
sp = 0;
}
}
}
cout << maxi;
return 0;
}
Mar 6, 2021 at 7:59pm UTC
I can't "repair" your code because I don't have a clue what you are doing.
In the code below, B[i][j] accumulates the sum of elements in a block from top left of the matrix to a bottom right at [i][j]. (Note that it is effectively 1-indexed).
The code then just scans all blocks delimited by (i1,j1) (not-included) to (i2,j2) (as bottom right-hand corner).
I expect that there is a better way.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int rows, cols;
cin >> rows >> cols;
vector< vector<int > > B( 1 + rows, vector<int >( 1 + cols, 0 ) );
vector<int > colsum( 1+cols, 0 );
for ( int i = 1; i <= rows; i++ )
{
for ( int j = 1; j <= cols; j++ )
{
int a;
cin >> a;
colsum[j] += a;
B[i][j] = B[i][j-1] + colsum[j];
}
}
int Smax = B[1][1];
for ( int i2 = 1; i2 <= rows; i2++ )
for ( int j2 = 1; j2 <= cols; j2++ )
for ( int i1 = 0; i1 < i2; i1++ )
for ( int j1 = 0; j1 < j2; j1++ )
Smax = max( Smax, B[i2][j2] - B[i1][j2] - B[i2][j1] + B[i1][j1] );
cout << Smax;
}
maximumSubmatrix.exe < in1
8
maximumSubmatrix.exe < in2
-1
maximumSubmatrix.exe < in3
12
Last edited on Mar 7, 2021 at 5:15pm UTC
Topic archived. No new replies allowed.