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.

Answer 1

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

}