Fişierul intrare/ieşire:ssm.in, ssm.outSursăInfoarena
AutorTeorieAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Subsecvenţa de sumă maximă

Se dă un şir S[ ] = (s1, s2, ..., sN) de lungime N . O subsecvenţă a şirului este de forma: (si, si+1, ..., sj) cu 1 ≤ i ≤ j ≤ N, iar suma subsecvenţei este si + si+1 + ... + sj.

Cerinţă

Se cere să se determine subsecvenţa de sumă maximă.

Date de intrare

Fişierul de intrare ssm.in conţine pe prima linie un număr natural N, reprezentând lungimea şirului. Următoarea linie conţine N numere întregi separate printr-un spaţiu, reprezentând în ordine elementele şirului.

Date de ieşire

În fişierul de ieşire ssm.out se vor tipări trei numere în această ordine: suma subsecvenţei de sumă maximă, indicele de început şi indicele de sfârşit.

Restricţii

  • 1 ≤ N ≤ 6 000 000
  • Pentru 20% dintre teste: 1 ≤ N ≤ 1 000
  • Pentru încă 20% dintre teste: 5 000 ≤ N ≤ 30 000
  • Pentru restul de 60%: 100 000 ≤ N ≤ 6 000 000
  • Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate cea mai scurtă.
  • Se garantează că toate rezultatele intermediare şi cel final vor putea fi reprezentate pe întregi cu semn pe 32 de biţi.

Exemplu

ssm.inssm.out
7
5 -6 3 4 -2 3 -3
8 3 6

Explicaţie

Subsecvenţa de sumă maximă este: (3, 4, -2, 3), a cărei sumă 3 + 4 - 2 + 3 = 8 este maximă dintre toate cele N *( N-1 )/ 2 subsecvenţe ce se pot forma.

Trebuie sa te autentifici pentru a trimite solutii. Click aici