h4. Exemplu

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

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

* $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:

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.

 
* $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.

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:

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,

 
* 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,
 

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:

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]))$.

 
* $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]))$.

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)$.