după care rezolvăm problema pentru sufix şi prefix prin metoda liniară în $O(N/K)$, şi determinăm în $O(1)$ pentru fiecare bucată în care este spart şirul $a[x..y]$ subsecvenţa ei de sumă maximă.

Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i < j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucată are valoarea: $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(K)$. Deci, pentru a rezolva o întrebare trebuie să facem $O(N/K + K)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $K = sqrt(N)$. Complexitatea totală a acestei soluţii este $O(N + M*sqrt(N))$.

Mai rămâne să găsim subsecvenţa de sumă maximă cu capătul în bucăţi diferite. Pentru două bucăţi fixate $i < j$, subsecvenţa de sumă maximă ce are câte un capăt în fiecare bucată are valoarea: $max[j] - min[i]$. Determinarea subsecvenţei de sumă maximă cu capetele în bucăţi diferite devine astfel de complexitate $O(K)$. Deci, pentru a rezolva o întrebare trebuie să facem $O(N/K + K)$ calcule. Pentru a reduce complexitatea problemei considerăm pe $K = sqrt(N)$. Complexitatea totală a acestei soluţii este $O(N + M * sqrt(N))$.

Să vedem ce se întâmplă pe exemplu:

        build_tree(2 * index + 1, mid + 1, high);
        aint[index].maxS = Math.max(aint[2 * index].maxS,
                Math.max(aint[2 * index + 1].maxS, aint[2 * index + 1].max - aint[2 * index].min));

        aint[index].max = Math.max(aint[2 * index].max,aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min,aint[2 * index + 1].min);

        aint[index].max = Math.max(aint[2 * index].max, aint[2 * index + 1].max);
        aint[index].min = Math.min(aint[2 * index].min, aint[2 * index + 1].min);

    }
}
==

şi procedura care răspunde la întrebări tot în _java_:
== code(java) |

long minPrefix;

long minPrefix;

int x, y;
public long queryTree(int index, int low, int high) {
    if (x <= low && high <= y) {
        long maxRet = aint[index].maxS;

        if (minPrefix != infinity) {

        if (minPrefix != INFINIT) {

            maxRet = Math.max(maxRet, aint[index].max - minPrefix);
        }
        minPrefix = Math.min(minPrefix, aint[index].min);

h2(#bibliografie). Bibliografie

# '_Arbori de intervale (Segment Trees)_':arbori-de-intervale, Dana Lica
# '_Căutări Ortogonale: Structuri de date şi aplicaţii_':cautari-ortogonale, Cosmin Negruşeri
# '_Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication_':http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf, Takaoka T.
# '_On the Range Maximum-Sum Segment Query_':http://www.csie.ntu.edu.tw/~kmchao/papers/2007_DAM_RMSQ.pdf, Kuan Yu Chen, 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, Yaw Ling Liu, Tao Jiang, Kun Mao Chao
# '_Introducere in Algoritmi_':http://zhuzeyuan.hp.infoseek.co.jp/ita/toc.htm, T. H. Cormen, C. E. Leiserson, R. R. Rivest

# Dana Lica - '_Arbori de intervale şi aplicaţii în geometria computaţională_':arbori-de-intervale
# Cosmin Negruşeri - '_Căutări Ortogonale: Structuri de date şi aplicaţii_':cautari-ortogonale
# 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