Fişierul intrare/ieşire:ssm.in, ssm.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test1.6 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

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 ≤ 6 000 000
  • Pentru 20% dintre teste: 1 ≤ N ≤ 1 000.
  • Pentru încă 20%: 5 000 ≤ N ≤ 30 000.
  • Pentru restul de 60%: 100 000 ≤ N ≤ 6 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.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.

Indicaţii de rezolvare

Un articol excelent care tratează această problemă şi numeroase alte probleme cu secvenţe se găseşte la această adresă.

Soluţia cea mai simplă constă în fixarea celor doi indici, de început şi de sfârşit, şi calcularea sumei pe acest interval. Soluţia are complexitatea O(N3) şi obţine 20p.

Dacă fixăm începutul secvenţei iar în timp ce iterăm cu al doilea indice calculăm şi suma secvenţei, obţinem o soluţie în complexitate O(N2) ce obţine 40p.

Volumul mare de date permite acestei soluţii să obţină 70-85p în complexitate O(N*log(N)), depinzând de tipul funcţiilor folosite pentru citirea datelor. Recomandăm folosirea streamurilor din C++ în locul funcţiilor de citire din librăria limbajului C. Soluţia foloseşte metoda Divide et Impera. Un interval [i, j] îl împărţim în două: [i, mid] şi [mid + 1, j] unde mid = (i + j) / 2, calculăm subsecvenţa de sumă maximă în cele două intervale şi apoi le combinăm prin alegerea unei subsecvenţe care este suma dintre subsecvenţa de sumă maximă ce se termină pe poziţia mid în intervalul [i, mid] şi a celei care începe pe poziţia mid + 1 în intervalul [mid + 1, j].

Prima soluţie ce obţine 100p în complexitate O(N) foloseşte următoarea idee: notând cu Si suma tuturor valorile din şir de pe poziţiile 1 .. i atunci suma maximă a unei subsecvenţe ce se termină pe poziţia i este Max(Si - Sj), j < i care este echivalentă cu Si - Min(Sj), j < i. Rezultă că va trebui doar să reţinem minimul dintre toate sumele parţiale Sj cu j < i.

Cea de a doua soluţie ce obţine 100p foloseşte metoda Programării dinamice. Construim un şir besti egal cu costul subsecvenţei de sumă maximă ce se termină pe poziţia i. Rezultă recurenţa următoare: besti = Max(besti-1 + si, si). Rezultă mai departe că si este sfârşitul unei subsecvenţe ce se extinde spre stânga cu subsecvenţa de sumă maximă ce se termină în si-1 doar dacă această subsecvenţă are suma pozitivă. În implementare nu este necesar să reţinem întregul vector best, ci doar o variabilă, după cum se vede şi în sursă. Complexitate: O(N).

Multe dintre soluţiile de mai sus pot fi rezolvate cu O(1) memorie. Iată un exemplu pentru a doua soluţie de 100p.

Probleme suplimentare

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content