Question

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

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int s[1000][1000];

int main(){

int n,m,x;

cin >> n >> m;

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

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

  cin >> x;

  s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + x;

 }

}

int smax = 0, s_;

int i_1, i_2, j_1, j_2;

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

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

  for(register int dx = 0; dx < m - j; dx++){

   for(register int dy = 0; dy < n - i; dy++){

    s_ = s[i+dy][j+dx] - s[i-1][j+dx] - s[i+dy][j-1] + s[i-1][j-1];

    if(s_ > smax){

     smax = s_;

     i_1 = i+1;

     i_2 = i+1+dy;

     j_1 = j+1;

     j_2 = j+1+dx;

    }

   }

  }

 }

}

cout << smax << '\n' << i_1 << ' ' << j_1 << ' ' << i_2 << ' ' << j_2;

}

Explicație:

Se folosesc sume partiale pe matrice.