Soluţia problemei Minmax
10 puncte (n^n)
Putem genera toate partiţiile şirului, apoi pentru fiecare partiţie să verificăm dacă suma obţinută pentru aceasta partiţie este mai mare decât răspunsul pentru numărul de subşiruri al acesteia.
20 de puncte (3^n*n)
Vom folosi o dinamică pe stări exponenţiale maxim[nr][configuratie]. configuratie_subsir reprezintă un număr al cărui biţi setaţi la 1 indică elementele care apar în oricare din primele nr subşiruri.
Recurenţa obţinută va fi:
- dp[nr][configuratie] = max { dp[nr-1][configuratie^subsir]+dif[subsir] | subsir este o submască a numărului configuratie }
- dif[subsir] reprezintă diferenţa între maxim şi minim în subşirul subsir.
Cu precalculări pentru valorile dif, putem ajunge la o soluţie în O(n* 3^n).
40 de puncte (n^2)
Observăm următoarea relaţie:
suma {max(subsir)-min(subsir)| subsir e in partitie} = suma {max(subsir)| subsir e in partitie} - suma {min(subsir)| subsir e in partitie}
Cu alte cuvinte, cele 2 componente sunt independente şi pot fi calculate separat. Putem mereu sa luam aceste elemente, iar cele ce se afla intre ele sa le punem intr-un subsir arbitrar, deoarece nu influenteaza raspunsul.
Astfel, problema se reduce la a găsi suma maxima a k elemente din subşir şi a scădea din ea suma minimă a k elemente din subşir pentru un k fixat. Putem găsi aceste valori cu programare dinamică
( max[poz][cate] - suma maximă până la poziţia poz cu cate elemente, analog şi pentru minim, min[poz][cate]). Recurenţa nu este foarte dificilă şi o recomandăm ca exerciţiu.
100 de puncte (n * log n)
Facem urmatoarea observatie: cele mai mari k valori din sir sunt ultimele k in sir dupa sortare, iar cele mai mici primele k dupa sortare.
Acum problema se reduce la a calcula niste sume pe prefixul, respectiv sufixul unui sir, problema ce poate fi rezolvata in O(n) cu sume partiale, sau prin calculare explicita deoarece 2 raspunsuri consecutive difera doar prin 2 elemente adaugate.
