Subșir crescător maximal
Cerință:
Fie un vector a cu N elemente. Numim subșir al lui a de lungime K un vector a' = (ai1, ai2, ..., aiK) astfel încât să avem i1 < i2 < ... < iK. Să se determine un subșir al lui a care este ordonat strict crescător si care are lungimea maximă.
Rezolvare:
O prima rezolvare ce utilizează programarea dinamică ar fi să se noteze besti - lungimea maximă a unui subșir crescător care se termină pe poziția i . Obținem astfel următoarea relație de recurentă: besti = 1 + max(bestj) cu 1 ≤ j < i si aj < ai . Pentru a reconstrui soluția mai reținem un vector cu semnificația prei - poziția valorii care preceda elementul i in subșirul crescător care se termină pe poziția i. Complexitate: O(N^2) timp și O(N) memorie.
#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
int V[maxn], Best[maxn], Pre[maxn];
int main() {
int n, i, j, maxx, p;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> V[i];
}
Best[n] = 1; Pre[n] = -1;
maxx = 1; p = n;
for (i = n - 1; i; i--) {
Best[i] = 1;
Pre[i] = -1;
for (j = i + 1; j <= n; j++) {
if (Best[j] + 1 > Best[i] && V[j] > V[i]) {
Best[i] = Best[j] + 1;
Pre[i] = j;
}
if (Best[i] > maxx) {
maxx = Best[i];
p = i;
}
}
}
cout << maxx << "\n";
i = p;
while (i != -1) {
cout << V[i] << " ";
i = Pre[i];
}
return 0;
}
Soluția optimă are complexitate O(N*logN) timp și O(N) memorie. Ea se bazează pe căutarea binară a celei mai mari lungimi bestj pe intervalul [1, lg_max]. Acest interval se extinde de fiecare dată când este îmbunătățită soluția. Implementarea este puțin mai dificil de înțeles decât cea anterioară, însă în practică se mișcă mult mai rapid.
#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
int Best[maxn], Pre[maxn], V[maxn], maxx;
inline int Bin_search(int val) {
int left = 1, right = maxx, mid;
while (left <= right) {
mid = (left + right) >> 1;
if (V[Best[mid]] < val) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return left;
}
void Secventa(int x) {
if(Pre[x]) {
Secventa(Pre[x]);
}
cout << V[x] << " ";
}
int main() {
ios_base :: sync_with_stdio (false);
int n, i, pos;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> V[i];
}
for (i = 1; i <= n; i++) {
pos = Bin_search(V[i]);
maxx = max(maxx, pos);
Best[pos] = i;
Pre[i] = Best[pos - 1];
}
cout << maxx << "\n";
Secventa(Best[maxx]);
return 0;
}