Бузургтарин зерпайдарпаии афзоянда (БЗА)
Дода шудааст пайдарпайии . Талаб мешавад зерпайдарпайии афзояндаи дарозии аз ҳама калонтарини онро ёфтан.
Масалан, зерпайдарпайии афзояндаи аз ҳама калонтарини ин мебошад.
Нусхаи пайдарпайии -ро месозем ва онро ба тартиби афзоишӣ ҷудо мекунем. Бигӯем ин аст. Он гоҳ ҷавоб барои масъалаи аслӣ НОП-и пайдарпайиҳои ва мебошад.
-ро ҳамчун ҳал барои префикси массиви бо дарозии бо шарте, ки элементи дар мавқеи буда ба ҷавоб дохил шудааст, ишора мекунем. Яъне, дарозии зерпайдарпайии афзояндаи аз ҳама калонтарини , ки дар он ба ҷавоб дохил шудааст.
Ҳолати базавӣ ин аст:
Акнун кӯшиш мекунем гузаришҳоро барои ҳолати умумии ёбем. Биёед гузаришҳоро баррасӣ кунем. Аз рӯи таърифи мо бояд -ро ба ҷавоб дохил кунем. Яъне, элементи охирини зерпайдарпайии афзояндаи префикси ин аст. Он гоҳ ду ҳолат дорем:
Пас, формуларо дорем:
Ҷавоб арзиши максималии дар байни ҳамаи хоҳад буд.
Биёед барои ҳар як ҳолати ғайрибазавӣ гузариши беҳтаринро ҳамон тавре ки дар ҳолати НОП дар хотир нигоҳ дорем. Яъне, инчунин массиви -ро месозем, ки дар он маълумотро дар бораи он ки кадом гузариш анҷом дода шудааст, нигоҳ медорем. Мо медонем, ки ду гузариши гуногун дорад:
Пас аз ин акнун мо метавонем ҷавобро барқарор кунем. Чунин -ро меёбем, ки барои он арзиши максималӣ дорад. Ва то он даме ки бошад, корҳои зеринро мекунем.
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
for (int i = 1; i <= n; i++) {
dp[i] = 1;
p[i] = 0;
for (int j = 1; j < i; j++) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
p[i] = j;
}
}
}
int x = 1;
for (int i = 1; i <= n; i++) {
if (dp[i] > dp[x]) {
x = i;
}
}
vector<int> res;
while (x > 0) {
res.push_back(a[x]);
x = p[x];
}
reverse(res.begin(), res.end());