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':job_detail/257844?action=view-source în complexitate $O(N^2^)$ ce obţine $40p$.
Volumul mare de date permite 'acestei soluţiei':job_detail/257845?action=view-source 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]$.
Volumul mare de date permite 'acestei soluţii':job_detail/257845?action=view-source 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':job_detail/257848?action=view-source ce obţine $100p$ în complexitate $O(N)$ foloseşte următoarea idee: notând cu $S{~i~}$ 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(S{~i~} - S{~j~}), j < i$ care este echivalentă cu $S{~i~} - Min(S{~j~}), j < i$. Rezultă că va trebui doar să reţinem minimul dintre toate sumele parţiale $S{~j~}$ cu $j < i$.
'Cea de a doua soluţie':job_detail/257847?action=view-source ce obţine $100p$ foloseşte metoda _Programării dinamice_. Construim un şir $best{~i~}$ egal cu costul subsecvenţei de sumă maximă ce se termină pe poziţia $i$. Rezultă recurenţa următoare: $best{~i~} = Max(best{~i-1~} + s{~i~}, s{~i~})$. Rezultă mai departe că $s{~i~}$ este sfârşitul unei subsecvenţe ce se extinde spre stânga cu subsecvenţa de sumă maximă ce se termină în $s{~i-1~}$ doar dacă această subsecvenţă are suma pozitivă. În implementare nu este necesar să reţinem întregul vector $best{~i~}$, după cum se vede şi în sursă. Complexitate: $O(N)$.
'Cea de a doua soluţie':job_detail/257847?action=view-source ce obţine $100p$ foloseşte metoda _Programării dinamice_. Construim un şir $best{~i~}$ egal cu costul subsecvenţei de sumă maximă ce se termină pe poziţia $i$. Rezultă recurenţa următoare: $best{~i~} = Max(best{~i-1~} + s{~i~}, s{~i~})$. Rezultă mai departe că $s{~i~}$ este sfârşitul unei subsecvenţe ce se extinde spre stânga cu subsecvenţa de sumă maximă ce se termină în $s{~i-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':job_detail/257846?action=view-source pentru a doua soluţie de $100p$.
