Хамгийн урт өсөх дэд дараалал¶
Бидэнд $n$ тоо бүхий массив өгөгдсөн: $a[0 \dots n-1]$. Даалгавар нь $a$ дахь хамгийн урт, чанд өсөх дэд дарааллыг олох явдал юм.
Албан ёсоор бид дараах байх $i_1, \dots i_k$ индексүүдийн хамгийн урт дарааллыг хайна
Энэ өгүүлэлд бид энэ даалгаврыг бодох хэд хэдэн алгоритмыг авч үзнэ. Мөн энэ бодлогод шилжүүлж болох бусад зарим бодлогыг авч үзнэ.
Динамик программчлалаар $O(n^2)$-д бодох¶
Динамик программчлал бол асар их төрлийн бодлогыг бодох боломж олгодог маш ерөнхий арга юм. Энд бид энэ аргыг өөрсдийн тодорхой даалгаварт хэрэглэнэ.
Эхлээд бид зөвхөн хамгийн урт өсөх дэд дарааллын урт-ыг хайх ба зөвхөн дараа нь дэд дарааллыг өөрийг нь хэрхэн сэргээхийг сурна.
Уртыг олох¶
Энэ даалгаврыг гүйцэтгэхийн тулд бид $d[0 \dots n-1]$ массивыг тодорхойлно, энд $d[i]$ нь $i$ индекс дэх элементээр төгсдөг хамгийн урт өсөх дэд дарааллын урт юм.
Example
4-р индексээр төгсдөг хамгийн урт өсөх дэд дараалал нь $\{3, 4, 5\}$ бөгөөд урт нь 3, 8-р индексээр төгсдөг хамгийн урт нь $\{3, 4, 5, 7, 9\}$ эсвэл $\{3, 4, 6, 7, 9\}$ бөгөөд хоёул урт нь 5, 9-р индексээр төгсдөг хамгийн урт нь $\{0, 1\}$ бөгөөд урт нь 2 юм.
Бид энэ массивыг аажмаар тооцоолно: эхлээд $d[0]$, дараа нь $d[1]$ гэх мэтчилэн. Энэ массивыг тооцоолсны дараа бодлогын хариу нь $d[]$ массив дахь хамгийн их утга байна.
Тэгэхээр одоогийн индекс $i$ байг. Өөрөөр хэлбэл бид $d[i]$ утгыг тооцоолохыг хүсэж байгаа бөгөөд өмнөх бүх утгууд $d[0], \dots, d[i-1]$ аль хэдийн мэдэгдэж байгаа. Тэгвэл хоёр сонголт бий:
-
$d[i] = 1$: шаардлагатай дэд дараалал зөвхөн $a[i]$ элементээс тогтоно.
-
$d[i] > 1$: Дэд дараалал $a[i]$-ээр төгсөх ба яг түүний өмнө $j < i$ ба $a[j] < a[i]$ байх ямар нэг $a[j]$ тоо байна.
$a[j]$-ээр төгсдөг дэд дараалал нь өөрөө $a[j]$-ээр төгсдөг хамгийн урт өсөх дэд дарааллуудын нэг байх нь харахад амархан. $a[i]$ тоо тэрхүү хамгийн урт өсөх дэд дарааллыг ердөө нэг тоогоор өргөтгөнө.
Тиймээс бид $a[j] < a[i]$ байх бүх $j < i$-ээр давтаж, $a[j]$-ээр төгсдөг хамгийн урт өсөх дэд дараалалд $a[i]$-г залгаснаар олж авах хамгийн урт дарааллыг авч болно. $a[j]$-ээр төгсдөг хамгийн урт өсөх дэд дараалал нь $d[j]$ урттай, түүнийг нэгээр өргөтгөвөл $d[j] + 1$ урт гарна.
$$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$
Хэрэв бид эдгээр хоёр тохиолдлыг нэгтгэвэл $d[i]$-ийн эцсийн хариуг олж авна:
Implementation¶
Here is an implementation of the algorithm described above, which computes the length of the longest increasing subsequence.
int lis(vector<int> const& a) {
int n = a.size();
vector<int> d(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i])
d[i] = max(d[i], d[j] + 1);
}
}
int ans = d[0];
for (int i = 1; i < n; i++) {
ans = max(ans, d[i]);
}
return ans;
}
Дэд дарааллыг сэргээх¶
Одоог хүртэл бид зөвхөн дэд дарааллын уртыг хэрхэн олохыг сурсан боловч дэд дарааллыг өөрийг нь хэрхэн олохыг сураагүй.
Дэд дарааллыг сэргээхийн тулд бид $d[]$ массивтай зэрэгцүүлэн тооцоолох нэмэлт туслах массив $p[0 \dots n-1]$-г үүсгэнэ. $p[i]$ нь $i$-ээр төгсдөг хамгийн урт өсөх дэд дараалал дахь сүүлээсээ хоёр дахь элементийн $j$ индекс байна. Өөрөөр хэлбэл $p[i]$ индекс нь $d[i]$ хамгийн их утга олдсон тэрхүү $j$ индекстэй ижил. Энэ туслах массив $p[]$ нь тодорхой утгаараа өвгүүд рүү заана.
Дараа нь дэд дарааллыг гаргахын тулд бид зүгээр л хамгийн их $d[i]$-тэй $i$ индексээс эхэлж, бүхэл дэд дарааллыг гаргах хүртэл буюу $d[i] = 1$ байх элементэд хүрэх хүртэл өвгүүдийг дагана.
Implementation of restoring¶
We will change the code from the previous sections a little bit. We will compute the array $p[]$ alongside $d[]$, and afterwards compute the subsequence.
For convenience we originally assign the ancestors with $p[i] = -1$. For elements with $d[i] = 1$, the ancestors value will remain $-1$, which will be slightly more convenient for restoring the subsequence.
vector<int> lis(vector<int> const& a) {
int n = a.size();
vector<int> d(n, 1), p(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
p[i] = j;
}
}
}
int ans = d[0], pos = 0;
for (int i = 1; i < n; i++) {
if (d[i] > ans) {
ans = d[i];
pos = i;
}
}
vector<int> subseq;
while (pos != -1) {
subseq.push_back(a[pos]);
pos = p[pos];
}
reverse(subseq.begin(), subseq.end());
return subseq;
}
Дэд дарааллыг сэргээх өөр арга¶
$p[]$ туслах массивгүйгээр дэд дарааллыг сэргээх боломжтой. Бид зүгээр л $d[i]$-ийн одоогийн утгыг дахин тооцоолж, максимум хэрхэн хүрснийг харж болно.
Энэ арга нь бага зэрэг урт код руу хүргэдэг боловч хариуд нь бид бага зэрэг санах ой хэмнэнэ.
Динамик программчлал ба хоёртын хайлтаар $O(n \log n)$-д бодох¶
Бодлогод илүү хурдан шийдэл олж авахын тулд бид $O(n^2)$-д ажилладаг өөр динамик программчлалын шийдэл байгуулж, дараа нь түүнийг $O(n \log n)$ хүртэл сайжруулна.
Бид $d[0 \dots n]$ динамик программчлалын массивыг ашиглана. Энэ удаад $d[l]$ нь $a[i]$ элемент буюу массивын угтварт харгалзахгүй. $d[l]$ нь $l$ урттай өсөх дэд дараалал төгсдөг хамгийн бага элемент байна.
Эхэндээ бид $d[0] = -\infty$ гэж үзэх ба бусад бүх уртын хувьд $d[l] = \infty$.
Бид дахин тоонуудыг аажмаар боловсруулна, эхлээд $a[0]$, дараа нь $a[1]$ гэх мэт, ба алхам бүрд $d[]$ массивыг шинэ хэвээр байлгана.
Example
$a = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\}$ массив өгөгдсөн үед тэдгээрийн бүх угтвар ба тэдгээрийн динамик программчлалын массив энд байна. Массивын утгууд төгсгөлдөө үргэлж өөрчлөгддөггүйг анхаарна уу.
$a[i]$-г боловсруулахдаа бид өөрсдөөсөө асууж болно. Одоогийн $a[i]$ тоог $d[0 \dots n]$ массивт бичихийн тулд ямар нөхцөл байх ёстой вэ?
Хэрэв $a[i]$-ээр төгсдөг $l$ урттай хамгийн урт өсөх дараалал байгаа бөгөөд илүү бага тоогоор төгсдөг $l$ урттай хамгийн урт өсөх дараалал байхгүй бол бид $d[l] = a[i]$ гэж тавина. Өмнөх аргатай адил, хэрэв бид $l$ урттай хамгийн урт өсөх дарааллаас $a[i]$ тоог хасвал бид $l -1$ урттай өөр нэг хамгийн урт өсөх дараалал олж авна. Тиймээс бид $l - 1$ урттай хамгийн урт өсөх дарааллыг $a[i]$ тоогоор өргөтгөхийг хүсэж байгаа бөгөөд хамгийн бага элементээр төгсдөг $l - 1$ урттай хамгийн урт өсөх дараалал хамгийн сайн ажиллах нь ойлгомжтой, өөрөөр хэлбэл $d[l-1]$ элементээр төгсдөг $l-1$ урттай дараалал.
$d[l-1] < a[i]$ байвал, яг тэр үед л бид $a[i]$ тоогоор өргөтгөж болох $l - 1$ урттай хамгийн урт өсөх дараалал байна. Тиймээс бид зүгээр л урт $l$ бүрээр давтаж, шалгуурыг шалгах замаар $l - 1$ урттай хамгийн урт өсөх дарааллыг өргөтгөж чадах эсэхийг шалгаж болно.
Түүнчлэн бид төгсгөлдөө илүү бага тоотой $l$ урттай хамгийн урт өсөх дарааллыг аль хэдийн олсон эсэхийг мөн шалгах хэрэгтэй. Тиймээс бид зөвхөн $a[i] < d[l]$ бол шинэчилнэ.
$a[]$-ийн бүх элементийг боловсруулсны дараа хайж буй дэд дарааллын урт нь $d[l] < \infty$ байх хамгийн их $l$ болно.
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> d(n+1, INF);
d[0] = -INF;
for (int i = 0; i < n; i++) {
for (int l = 1; l <= n; l++) {
if (d[l-1] < a[i] && a[i] < d[l])
d[l] = a[i];
}
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}
Одоо бид хоёр чухал ажиглалт хийе.
-
$d$ массив үргэлж эрэмбэлэгдсэн байна: бүх $i = 1 \dots n$-ийн хувьд $d[l-1] < d[l]$.
Энэ нь тривиаль, учир нь та $l$ урттай өсөх дэд дараалалаас сүүлийн элементийг зүгээр л хасаж, төгсгөлийн тоо нь илүү бага $l-1$ урттай өсөх дэд дараалал олж авна.
-
$a[i]$ элемент хамгийн ихдээ ганц $d[l]$ утгыг шинэчилнэ.
Энэ нь дээрх хэрэгжүүлэлтээс шууд гарна. Массивт $d[l-1] < a[i] < d[l]$ байх ердөө нэг л байр байж болно.
Тиймээс бид энэ элементийг $d[]$ массиваас хоёртын хайлт ашиглан $O(\log n)$-д олж болно. Үнэн хэрэгтээ бид $d[]$ массиваас $a[i]$-ээс чанд их эхний тоог зүгээр л хайж, дээрх хэрэгжүүлэлттэй ижил байдлаар энэ элементийг шинэчлэхийг оролдож болно.
Implementation¶
This gives us the improved $O(n \log n)$ implementation:
int lis(vector<int> const& a) {
int n = a.size();
const int INF = 1e9;
vector<int> d(n+1, INF);
d[0] = -INF;
for (int i = 0; i < n; i++) {
int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
if (d[l-1] < a[i] && a[i] < d[l])
d[l] = a[i];
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}
Дэд дарааллыг сэргээх¶
Энэ аргыг ашиглан дэд дарааллыг мөн сэргээх боломжтой. Энэ удаад бид хоёр туслах массив хадгалах ёстой. Нэг нь $d[]$ дахь элементүүдийн индексийг бидэнд хэлнэ. Мөн дахин бид "өвгүүд"-ийн массив $p[i]$-г үүсгэх ёстой. $p[i]$ нь $i$ элементээр төгсдөг оновчтой дэд дарааллын өмнөх элементийн индекс байна.
$a[]$ массиваар давтах явцад $d[]$-ийн тооцооллуудтай зэрэгцүүлэн эдгээр хоёр массивыг хадгалах нь амархан. Эцэст нь эдгээр массивыг ашиглан хайж буй дэд дарааллыг сэргээхэд хэцүү биш.
Өгөгдлийн бүтэц ашиглан $O(n \log n)$-д бодох¶
Хамгийн урт өсөх дэд дарааллыг $O(n \log n)$-д тооцоолох дээрх аргын оронд бид бодлогыг өөр аргаар: зарим энгийн өгөгдлийн бүтэц ашиглан бас бодож болно.
Эхний арга руу буцъя. $d[i]$ нь $j < i$ ба $a[j] < a[i]$ байх $d[j] + 1$ утга гэдгийг сана.
Тиймээс хэрэв бид дараах байх нэмэлт массив $t[]$-г тодорхойлбол
$d[i]$ утгыг тооцоолох бодлого нь $t[]$ массивын угтвар дахь хамгийн их утга-г олохтой эквивалент болно:
Массивын (өөрчлөгддөг) угтварын максимумыг олох бодлого нь олон янзын өгөгдлийн бүтцээр бодогдож болох стандарт бодлого юм. Жишээ нь бид хэрчмийн мод эсвэл Фенвикийн мод ашиглаж болно.
Энэ арга нь илэрхий зарим сул тал-тай: хэрэгжүүлэлтийн урт ба complexity-ийн хувьд энэ арга нь хоёртын хайлт ашигласан аргаас муу байна. Түүнчлэн хэрэв оролтын $a[i]$ тоонууд онцгой том бол бид зарим арга, жишээ нь тоонуудыг шахах ($0$-ээс $n-1$ хүртэл дахин дугаарлах), эсвэл динамик хэрчмийн мод (зөвхөн чухал модны салаануудыг үүсгэх) ашиглах шаардлагатай болно. Эс бөгөөс санах ойн зарцуулалт хэт өндөр болно.
Нөгөө талаас энэ арга нь мөн зарим давуу тал-тай: энэ аргаар та динамик программчлалын шийдэл дэх ямар нэг заль мэхтэй шинж чанарын талаар бодох шаардлагагүй. Мөн энэ арга нь бодлогыг маш амархан ерөнхийлөх боломж олгоно (доор үзнэ үү).
Холбогдох бодлогууд¶
Хамгийн урт өсөх дэд дараалал олох бодлоготой нягт холбоотой хэд хэдэн бодлого энд байна.
Хамгийн урт буурахгүй дэд дараалал¶
Энэ нь үнэндээ бараг ижил бодлого юм. Зөвхөн одоо дэд дараалалд ижил тоонуудыг ашиглахыг зөвшөөрнө.
Шийдэл нь үндсэндээ мөн бараг ижил. Бид зүгээр л тэнцэтгэл бишийн тэмдгүүдийг өөрчилж, хоёртын хайлтад бага зэрэг өөрчлөлт хийх ёстой.
Хамгийн урт өсөх дэд дарааллуудын тоо¶
Бид эхний авч үзсэн арга буюу $O(n^2)$ хувилбар эсвэл өгөгдлийн бүтэц ашигласан хувилбарыг ашиглаж болно. Бид зөвхөн $d[i]$ утгуудаар төгсдөг хамгийн урт өсөх дэд дарааллуудыг хэдэн аргаар олж авч болохыг нэмж хадгалах ёстой.
$a[i]$-ээр төгсдөг хамгийн урт өсөх дэд дараалал үүсгэх аргын тоо нь $d[j]$ хамгийн их байх $j$-ээр төгсдөг бүх хамгийн урт өсөх дэд дарааллуудын бүх аргын нийлбэр юм. Ийм $j$ олон байж болох тул бид тэдгээрийг бүгдийг нийлбэрлэх хэрэгтэй.
Хэрчмийн мод ашиглан энэ аргыг мөн $O(n \log n)$-д хэрэгжүүлж болно.
Энэ даалгаварт хоёртын хайлтын аргыг ашиглах боломжгүй.
Дарааллыг бүрхэх өсөхгүй дэд дарааллуудын хамгийн бага тоо¶
$n$ тоо бүхий өгөгдсөн $a[0 \dots n - 1]$ массивын хувьд бид тоонуудыг хамгийн цөөн тооны өнгөөр будах ёстой бөгөөд өнгө бүр өсөхгүй дэд дараалал үүсгэнэ.
Үүнийг бодохын тулд шаардлагатай өнгөний хамгийн бага тоо нь хамгийн урт өсөх дэд дарааллын урттай тэнцүү болохыг бид анзаарна.
Баталгаа: Бид энэ хоёр бодлогын хос чанар (duality)-ыг батлах хэрэгтэй.
Хамгийн урт өсөх дэд дарааллын уртыг $x$, бүрхэлт үүсгэдэг өсөхгүй дэд дарааллуудын хамгийн бага тоог $y$ гэж тэмдэглэе. Бид $x = y$ гэдгийг батлах хэрэгтэй.
$y < x$ боломжгүй нь тодорхой, учир нь бид $x$ чанд өсөх элементтэй бол хоёр нь нэг өсөхгүй дэд дарааллын хэсэг байж чадахгүй. Тиймээс бид $y \ge x$ болно.
Одоо бид $y > x$ боломжгүйг зөрчлөөр харуулна. $y > x$ гэж үзье. Тэгвэл бид $y$ өсөхгүй дэд дарааллын дурын оновчтой олонлогийг авч үзнэ. Бид энэ олонлогийг дараах байдлаар хувиргана: эхнийх нь хоёр дахь дэд дарааллаас өмнө эхэлж, эхний дараалал нь хоёр дахиас их буюу тэнцүү тоогоор эхэлдэг ийм хоёр дэд дараалал байгаа л бол бид энэ эхлэлийн тоог салгаж, хоёр дахийн эхэнд залгана. Төгсгөлөг тооны алхмын дараа бид $y$ дэд дараалалтай болох ба тэдгээрийн эхлэлийн тоонууд $y$ урттай өсөх дэд дараалал үүсгэнэ. Бид $y > x$ гэж үзсэн тул бид зөрчилд хүрлээ.
Тиймээс $y = x$ гэж гарна.
Дарааллуудыг сэргээх: Дарааллыг дэд дараалуудад хайж буй хуваалтыг greedy-гээр хийж болно. Өөрөөр хэлбэл зүүнээс баруун тийш явж, одоогийн тоог одоогийнхоос их буюу тэнцүү хамгийн бага тоогоор төгсдөг тэрхүү дэд дараалалд ононо.