Наибольшая возрастающая подпоследовательность (НВП)
Дана последовательность . Требуется найти ее возрастающую подпоследовательность наибольшей длины.
Например, наибольшая возрастающая подпоследовательность является .
Создадим копию последовательности и отсортируем по возрастанию. Скажем это . Тогда ответом для исходной задачи является НОП последовательности и .
Обозначим как решением для префикса массива длины с условием, что элемент на позиции включен в ответ. Т.е. длину наибольшей возрастающей подпоследовательности где включен в ответ.
Базовый случай это:
Попытаемся теперь найти переходы для общего случая . Давайте разберем переходы. По определению мы должны включать в ответ . Т.е. последний элемент возрастающей подпоследовательности префикса это . Тогда имеем два случая:
Следовательно, имеем формулу:
Ответом будет максимальное значение среди всех .
Давайте для каждой не базовой состояний запомним наилучший переход также как в случае НОП. Т.е. также создадим массив где будем хранить информацию про то какой переход делалось. Мы знаем, что имеет два разных перехода:
После этого теперь мы можем восстановить ответ. Найдем такой для которой имеет максимальное значение. И будем делать следующее до тех пор, пока .
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());