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