Maximum submatrix

[bstroe]

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.

 #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;
}

[lastchance]

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.

#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