Зерпайдарпайии афзояндаи дарозтарин (ЗАД) бо $O(N \log N)$
Пештар мо ҳалли масъалаи LIS-ро бо истифода аз барномасозии динамикӣ баррасӣ карда будем, ки бо кор мекунад. Мо ба формулаи = дарозии дарозтарин зерпайдарпаии афзоянда, ки дар анҷом меёбад (ки дар он ба пайдарпаӣ дохил шудааст) расидем.
Барои ба даст овардани натиҷаи беҳтар аз , ба мо лозим аст, ки барои -и худ ҳолати дигарро интихоб кунем. Бигзор = хурдтарин элементе, ки дар он баъзе пайдарпаии афзояндаи дарозии анҷом меёбад. Дар оғоз массиви чунин менамояд:
Сипас мо элементҳои массивро як ба як коркард мекунем ва -и худро нав мекунем. Ҳангоми коркарди ба мо лозим аст барои ҳар як санҷем, ки оё мумкин аст пайдарпаии дарозии -ро бо истифода аз васеъ кунем. Ба таври расмӣ, барои ҳар як месанҷем, агар ва хурдтарин -ро интихоб мекунем, ки барои он ин дуруст аст, ва -ро ба ин қимат баробар мегузорем. Ба осонӣ дидан мумкин аст, ки чаро интихоби хурдтарин чунин оптималӣ мебошад.
Коркарди 4: Рақами 4 элементи аввал аст, бинобар ин ин хурдтарин рақамест, ки дар он зерпайдарпаии дарозии 1 анҷом меёбад.
Коркарди 1: Рақами 1 метавонад 4-ро дар массиви DP иваз кунад, зеро 1 хурдтар аст ва инчунин зерпайдарпаии дарозии 1-ро анҷом медиҳад.
Коркарди 3: Рақами 3 аз 1 калонтар аст, бинобар ин он дарозии зерпайдарпаиро то 2 зиёд мекунад. Акнун ин хурдтарин рақамест, ки зерпайдарпаии дарозии 2-ро анҷом медиҳад.
Коркарди 2: Рақами 2 аз 3 хурдтар ва аз 1 калонтар аст, бинобар ин он 3-ро дар массиви DP ҳамчун элементи охирини зерпайдарпаии дарозии 2 иваз мекунад.
Коркарди 5: Рақами 5 пайдарпаии афзояндаро зиёд мекунад; акнун ин хурдтарин рақамест, ки зерпайдарпаии дарозии 3-ро анҷом медиҳад.
Пас аз ин қадамҳо массиви нишон медиҳад, ки дарозтарин зерпайдарпаии афзоянда дарозии 3 дорад, ки ин бузургтарин индекс бо қимати камтар аз мебошад.
Бо такя ба ин мушоҳидаҳо, мо метавонем чунин -ро бо ёрии ҷустуҷӯи бинарӣ пайдо кунем. Мо мехоҳем аввалин элементро дар пайдо кунем, ки қатъиян аз калонтар аст. Ин на бештар аз вақт мегирад, бинобар ин, мо мураккабии умумии -ро ба даст меорем.
Биёед ба ҳолати аввалини , ки мо барои ҳалли ин масъала истифода бурдем, баргардем.
Ва биёед массиви нави -ро муайян кунем, чунин ки .
Акнун, барои ҳисоб кардани , ба мо лозим аст қимати максималӣ-ро дар префикси массиви пайдо кунем:
Инро ба осонӣ бо ёрии Дарахтони сегментӣ/Дарахтони Фенвик иҷро кардан мумкин аст.
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> dp(n+1, INF);
dp[0] = -INF;
for (int i = 0; i < n; i++) {
for (int l = 1; l <= n; l++) {
if (dp[l - 1] < a[i] && a[i] < dp[l])
dp[l] = a[i];
}
}
int ans = 1;
for (int l = 1; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> d(n + 1, INF);
dp[0] = -INF;
for (int i = 0; i < n; i++) {
int l = upper_bound(dp.begin(), dp.end(), a[i]) - d.begin();
if (dp[l - 1] < a[i] && a[i] < dp[l])
dp[l] = a[i];
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (dp[l] < INF)
ans = l;
}
return ans;
}