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, Bursele Agora)

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

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.