402
Se dă o matrice de numere întregi cu n
linii și n
coloane.
Cerința
Să se determine suma maximă care se poate obține dintr-o submatrice.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi elementele matricei cu n
linii și n
coloane.
Date de ieșire
Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice.
Restricții și precizări
1 ≤ n ≤ 300
- Elementele matricei sunt numere întregi din intervalul
[-1000, 1000]
- O submatrice poate fi formată dintr-un singur element
Exemplu
Intrare
5 2 4 -1 2 -1 4 -7 1 -6 -1 -9 2 4 5 -7 1 3 -2 6 2 1 -4 -6 -5 8
Ieșire
18
Explicație
Submatricea de sumă maximă este:
2 4 5
3 -2 6
#include <bits/stdc++.h> using namespace std; int n , a[301][301] , maxi , sp , b[301]; int main() { cin >> n; for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) { cin >> a[i][j]; a[i][j] += a[i - 1][j]; } maxi = -10000; for(int i = 1 ; i <= n ; i++) for(int j = i ; j <= n ; j++) { for(int k = 1 ; k <= n ; k++) b[k] = a[j][k] - a[i - 1][k]; int sp = 0; for(int k = 1 ; k <= n ; k++) { sp += b[k]; if(sp > maxi) maxi = sp; if(sp < 0) sp = 0; } } cout << maxi; return 0; }
Comentarii