Fișierul intrare/ieșire | maximumsum.in, maximumsum.out | Sursă | timus.ru |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Tiberiu Musat • Tiberiu02 |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Maximumsum
Dată o matrice de întregi negativi și pozitivi, găsiți submatricea de sumă maximă. Suma unei submatrice este suma tuturor elementelor din acea submatrice. În această problemă submatricea cu sumă maximă este denumită submatricea maximală. O submatrice este contiguă, de dimensiuni 1 × 1 sau mai mari și poate fi oriunde în matricea originală.
Ca exemplu, submatricea maximală a matricei:
este în colțul din stînga-jos și are sumă 15.
Date de intrare
Fișierul de intrare maximumsum.in conține pe prima linie un singur întreg pozitiv N, dimensiunea matricei. Pe următoarele N linii vor fi cîte N întregi separați prin spații, constituind elementele matricei.
Date de ieșire
Fișierul de ieșire maximumsum.out conține un singur număr, suma submatricei maximale.
Restricții
- N ≤ 320
- Numerele din matrice vor fi în intervalul [-127, 127].
Exemplu
maximumsum.in | maximumsum.out |
---|---|
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 |
15 |