Cel mai bun algoritm cunoscut pentru această problemă are complexitatea <tex>O(N^{3\sqrt{\frac{\log \log N}{\log N}}})</tex> şi este mai mult un algoritm teoretic decât unul practic, uşor implementabil. Pentru detalii puteti consulta lucrarea [3].

h2(#problema-3). Problema 3 ('SequenceQuery':problema/sequencequery)

h2(#problema-3). Problema 3 ('SequenceQuery':problema/sequencequery, Bursele Agora)

bq. Se consideră un şir $A = (a{~1~}, a{~2~}, ..., a{~N~})$, format din numere întregi $(-100.000 ≤ a{~i~} ≤ 100.000)$, şi $M$ perechi de numere $(x, y)$ $(1 ≤ N, M ≤ 100.000)$. Pentru fiecare pereche ordonată de indici $(x, y)$ trebuie determinată subsecvenţa de sumă maximă a subşirului $a{~x~}, a{~x+1~}, ..., a{~y~}$. Subsecvenţele alese trebuie să conţină cel puţin un element.

Autorul vă recomandă articolele [1] şi [2] pentru o înţelegere mai profundă a structurii de date numită arbori de intervale. Problema poate fi soluţionată şi în $O(N + M)$, dar algoritmul este mult prea complicat pentru un concurs de programare; cei interesaţi pot să îl găsească în [4].

h2(#problema-4). Problema 4 (ACM ICPC NWERC 97, olimpiada online 2000, campion 2001)

h2(#problema-4). Problema 4 (ACM ICPC NWERC 97, olimpiada online 2000, .campion 2001)

bq. Se dă un şir $(a{~1~}, a{~2~}, ..., a{~N~})$ format din numere întregi. Se cere să se determine subsecvenţa $a[i..j]$ care are modulul sumei elementelor minim.

* 'Struţi':problema/struti
* 'Deque':problema/deque
* 'Trie':problema/trie

* 'Maxq':problema/maxq

h2(#bibliografie). Bibliografie