Question

Se dă o matrice mt cu N linii și M coloane. Să se afle submatricea de sumă maximă din matrice. Sa se rezolve in C++ folosind sume partiale. 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

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int main(){

  int n, m, a[20][20], max;

  cin>>n>>m;

  for(int i = 0; i < n; i ++)

      for(int j = 0; j < m; j ++)

          cin>>a[i][j];

  max = a[0][0];

  for(int i = 0; i < n; i ++)

      for(int j = 0; j < m; j ++)

          for(int i2 = i; i2 < n; i2++)

              for(int j2 = j; j2 < m; j2++) {

                  int s = 0;

                  for(int k = i; k <= i2; k ++)

                      for(int l = j; l <= j2; l ++)

                          s += a[k][l];

                  if(s > max) max = s;

              }

  cout<<max;    

}