Prima rezolvare care ne vine în minte are complexitatea $O(N^3^)$ şi constă în determinarea sumei fiecărei subsecvenţe posibile şi reţinerea maximului acestor sume. Este evident că anumite sume parţiale sunt calculate de mai multe ori.

Putem reduce complexitatea la $O(N^2^)$ ţinând cont de faptul că suma subsecvenţei $a[i..j]$ este egală cu suma subsecvenţei $a[i..j-1]$, la care se adună $a[j]$. Păstrăm într-un şir $sum[i]$ suma elementelor din subsecvenţa $a[1..i]$. Pentru a determina suma elementelor din subsecvenţa $a[i..j]$ facem diferenţa: $sum[i] - sum[j-1]$.

Putem reduce complexitatea la $O(N^2^)$ ţinând cont de faptul că suma subsecvenţei $a[j..i]$ este egală cu suma subsecvenţei $a[j..i-1]$, la care se adună $a[i]$. Păstrăm într-un şir $sum[i]$ suma elementelor din subsecvenţa $a[1..i]$. Pentru a determina suma elementelor din subsecvenţa $a[j..i]$ facem diferenţa: $sum[i] - sum[j-1]$.

Ideea poate fi rafinată calculând pentru fiecare indice $i$ numărul $best[i]$, reprezentând subsecvenţa de sumă maximă cu capătul drept în $i$. Este uşor de observat că $best[i] = max(sum[i] - sum[j-1])$, unde $j$ ia valori de la $1$ la $i$. Relaţia anterioară se mai poate scrie: $best[i] = sum[i] - min(sum[j-1])$. Obţinem astfel un algoritm liniar care ne determină subsecvenţa de sumă maximă cerută.