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ă.

}
==

h2(#problema-2). Problema 2: 'Maximum Sum':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44 (UVa)

h2(#problema-2). Problema 2: 'Maximum Sum':http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44 (UVa)

bq. Se dă o matrice de dimensiuni $N x N$ cu elemente întregi. Se cere determinarea unei submatrici a cărei elemente au suma maximă.

h3. Rezolvare:

Construim întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ cu $(i != j)$ modulul sumei unei subsecvenţe din şir va fi $|sum[i] - sum[j]|$. Dacă $i < j$, atunci secvenţa va fi $a[i+1..j]$, iar dacă $j < i$, atunci secvenţa va fi $a[j+1 .. i]$. Astfel, pentru a găsi subsecvenţa de modul minim trebuie, de fapt, să găsim perechea de indici $i$ şi $j$ astfel ca $|sum[i] - sum[j]|$ să fie minim. Sortând şirul sumelor parţiale şi luând o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a găsi perechea $(i, j)$ pentru care $i < j$ şi $sum[j] - sum[i]$ este minim, trebuie ca $i$ să fie egal cu $j + 1$. Astfel obţinem un algoritm de complexitate $O(N * log N)$.

Construim întâi şirul sumelor parţiale. Pentru oricare două elemente $sum[i]$ şi $sum[j]$ cu $(i != j)$ modulul sumei unei subsecvenţe din şir va fi $|sum[i] - sum[j]|$. Dacă $i < j$, atunci secvenţa va fi $a[i+1..j]$, iar dacă $j < i$, atunci secvenţa va fi $a[j+1 .. i]$.
 
Astfel, pentru a găsi subsecvenţa de modul minim trebuie, de fapt, să găsim perechea de indici $i$ şi $j$ astfel ca $|sum[i] - sum[j]|$ să fie minim. Sortând şirul sumelor parţiale şi luând o pereche de indici $i < j$, atunci $sum[i] < sum[j]$, iar $|sum[j] - sum[i]| = sum[j] - sum[i]$. Pentru a găsi perechea $(i, j)$ pentru care $i < j$ şi $sum[j] - sum[i]$ este minim, trebuie ca $i$ să fie egal cu $j + 1$. Astfel obţinem un algoritm de complexitate $O(N * log N)$.

Să vedem cum merge pe exemplul prezentat:

# Takaoka T. - '_Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication_':http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf
# Kuan Yu Chen, Kun Mao Chao - '_On the Range Maximum-Sum Segment Query_':http://www.csie.ntu.edu.tw/~kmchao/papers/2007_DAM_RMSQ.pdf
# Yaw Ling Liu, Tao Jiang, Kun Mao Chao - '_Efficient Algorithms for Locating the Length-Constrained Heaviest Segments, with Applications to Biomolecolar Sequence Analysis_':http://www.csie.ntu.edu.tw/~kmchao/seq2003/mslc.pdf

# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm
 

# T. H. Cormen, C. E. Leiserson, R. R. Rivest - '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm