Question

Se dă o matrice mt cu N linii și M coloane. Să se afle submatricea de sumă maximă din matrice.

Date de intrare
De pe prima linie se citesc de la tastatură numerele N și M. De pe următoarele N linii se citesc M numere naturale care reprezintă elementele matricei.

Date de ieșire
Programul va afișa pe ecran suma maximă a unei submatrice.

Restricții
1 ≤ N,M ≤ 50
-3 000 ≤ mt[i][j] ≤ 3 000
Exemplu
Date de intrare Date de ieșire
4 4
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1 -1
4 4
-1 -1 -1 -1
-1 2 2 -1
-1 -1 -1 -1
-1 -1 -1 -1 4

Answer 1

#include <iostream>

#include <climits>

using namespace std;

int N,M,  i, j,a[500][500],b[500][500], maxim=INT_MIN;

int main(){

cin>>N>>M;

for(i=1; i<=N; ++i){

  for(j=1; j<=M; ++j)

    cin>>a[i][j];

for(i=1; i<=N; ++i)

  for(j=1; j<=M; ++j)

     {b[i][j]=b[i-1][j]+a[i][j];

      if(b[i][j]>maxim) {maxim=b[i][j];}

     }

cout<<maxim;

}