Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ssm.in, ssm.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.8 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Subsecventa de suma maxima
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 ≤ 5 000 000
- |Si| ≤ 1 000
- Pentru 20% dintre teste: 1 ≤ N ≤ 1 000.
- Pentru încă 20%: 5 000 ≤ N ≤ 50 000.
- Pentru restul de 60%: 100 000 ≤ N ≤ 5 000 000.
- Dacă există mai mult 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.in | ssm.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 secvenţe ce se pot forma.
Indicaţii de rezolvare
Un articol excelent care tratează această problemă şi numeroase altele cu secvenţe se găseşte la această adresă.
Probleme suplimentare
Problemele de mai jos se reduc la găsirea subsecvenţei de sumă maximă, dar restricţiile impuse asupra secvenţei necesită uneori folosirea unei structuri de date numită deque. Mai multe informaţii despre această structură găsiţi la această adresă.
- Maximum Sum, UVa
- Sum 2, Stelele Informaticii
- Secvenţă 2
- Secvenţă 3
- Secvenţă 4
