Fișierul intrare/ieșire maximumsum.in, maximumsum.out Sursă timus.ru
Autor autor necunoscut Adăugată de avatar Tiberiu02 Tiberiu Musat Tiberiu02
Timp de execuție pe test 0.5 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii