Sous-matrice maximale
Étant donnée une matrice d'entiers, vous devez calculer la sous-matrice dont la somme est la plus grande.
Entrée
La première ligne de l’entrée contient deux entiers : le nombre de lignes de la matrice
r et le nombre de colonnes c (1 ≤ r, c ≤ 50).Les
r lignes suivantes comportent chacune c entiers séparés par un espace. Ces entiers représentent les éléments de la matrice .Sortie
Le programme doit afficher un entier unique : la somme maximale d’une sous-matrice.
Exemples
Entrée | Sortie |
3 5
1 2 -3 4 -6
-1 3 -100 4 0
0 1 -2 0 100 | 104 |
Explication
1 | 2 | -3 | 4 | -6 |
-1 | 3 | -100 | 4 | 0 |
0 | 1 | -2 | 0 | 100 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB