h4. Exemplu

Pentru şirul $(-1, 2, 3, -2, 4, -3, 8, -3, 1)$ şi intervalele $[1, 5]$, $[4, 8]$ si $[6, 6]$ avem soluţiile:
 

Pentru sirul $(-1, 2, 3, -2, 4, -3, 8, -3, 1)$ si intervalele $[1, 5]$, $[4, 8]$ si $[6, 6]$ avem solutiile:

* $7$ pentru subsecvenţa $(-1, *2*, *3*, *-2*, *4*)$;

* $9$ pentru subsecvenţa $(-2, *4*, *-3*, *8*, -3)$;

* $-3$ pentru subsecvenţa $({*-3*})$.
h3. Rezolvare
Putem obţine un algoritm de complexitate $O(MN)$ folosind algoritmii liniari din prima problemă, dar să vedem cum putem reduce complexitatea folosind alte abordări. Mai întâi calculăm şirul $sum$ al sumelor parţiale, după care împărţim şirul în $k$ subsecvenţe de lungimi egale $[n/k]$, şi păstrăm următoarele informaţii pentru fiecare din ele:

 
* $max[i]$ - cea mai mare valoare $sum[j]$, unde $n/k * (i-1) < j <= n/k * i$;
 
* $min[i]$ - cel mai mic $sum[j-1]$, unde $n/k * (i-1) < j <= n/k * i$;
 
* $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.

1. $max[i]$ - cea mai mare valoare $sum[j]$, unde $n/k * (i-1) < j <= n/k * i$;
2. $min[i]$ - cel mai mic $sum[j-1]$, unde $n/k * (i-1) < j <= n/k * i$;
3. $best[i]$ - valoarea subsecventei de suma maxima a secventei curente.

Acum, pentru a afla subsecvenţa de sumă maximă a subsecvenţei $a[x..y]$ studiem cele două cazuri posibile:
1. Dacă elementele de indice $x$ şi $y$ aparţin aceleiaşi subsecvenţe, atunci putem găsi ceea ce căutăm folosind algoritmul liniar direct pe şirul $a[x..y]$ (complexitate $O(n/k)$).
2. Dacă nu sunt în aceeaşi secvenţă, atunci vom împărţi şirul $a[x..y]$ în:

 
* un prefix de subsecvenţă din cele ce aparţin partiţionării,
 
* un sufix de subsecvenţă,
 
* zero sau mai multe subsecvenţe complete ce aparţin partiţionării,
 

a) un prefix de subsecvenţă din cele ce aparţin partiţionării,
b) un sufix de subsecvenţă,
c) zero sau mai multe subsecvenţe complete ce aparţin partiţionării,

după care rezolvăm problema pentru sufix şi prefix prin metoda liniară ( {$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ăm 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))$.

Pentru a răspunde la întrebarea $[1, 5]$ trebuie să răspundem la cele două subsecvenţe componente $[1..3]$ şi $[4..5]$. Soluţia optimă pentru $[1..3]$ este $best[1] = 5$. Soluţia optimă pentru $[4..5]$ o determinăm folosind algoritmul liniar, ea fiind $4$. Acum, pentru a determina subsecvenţa de sumă maximă cu câte un capăt în fiecare interval folosim formula $max(sum[i]) - min(sum[j-1])$, unde $4 <= i <= 5$ şi $1 <= j <= 3$. Valoarea $max(sum[i])$ o găsim parcurgând intervalul $[4, 5]$ ca fiind $6$, iar valoarea $min(sum[j-1])$ o avem deja calculată în $min[1]$. De aici obţinem rezultatul $7$.
O soluţie similară poate fi obţinută cu ajutorul arborilor de intervale. Mai întâi creăm arborele de intervale. Pentru fiecare interval aflăm elementele $min$, $max$ şi $best$ astfel:

 
* $min[x..y] = minim(min[x..(x+y)/2], min[(x+y)/2 + 1 .. y])$;
 
* $max[x..y] = maxim(max[x..(x+y)/2], max[(x+y)/2 + 1 .. y])$;
 
* $best[x..y] = maxim(best[x..(x+y)/2], maxim(best[(x+y)/2 + 1 .. y], max[(x+y)/2 + 1 .. y] - min[x..(x+y)/2]))$.

1. $min[x..y] = minim(min[x..(x+y)/2], min[(x+y)/2 + 1 .. y])$;
2. $max[x..y] = maxim(max[x..(x+y)/2], max[(x+y)/2 + 1 .. y])$;
3. $best[x..y] = maxim(best[x..(x+y)/2], maxim(best[(x+y)/2 + 1 .. y], max[(x+y)/2 + 1 .. y] - min[x..(x+y)/2]))$.

Acum pentru a răspunde la întrebările din problemă fiecare interval va fi împărţit în $O(log N)$ subintervale canonice care apar în arborele de intervale. Apoi printr-o parcurgere asemănătoare celei din rezolvarea anterioară se poate obţine rezultatul pentru fiecare întrebare în $O(log N)$. Soluţia va avea complexitatea $O(N + M log N)$.