988. Подпоследовательности

Для заданной последовательности найдите длину наибольшей строго возрастающей подпоследовательности.

Вход. Первая строка содержит длину n (1 ≤ n ≤ 1000) последовательности. Вторая строка содержит саму последовательность. Числа последовательности – целые числа, не превосходящие 10⁴ по модулю.

Выход. Выведите длину наибольшей строго возрастающей подпоследовательности.

Пример входа	Пример выхода
6 3 29 5 5 28 6	3

РЕШЕНИЕ

наибольшая возрастающая подпоследовательность

Анализ алгоритма

Решение за O(n²). В задаче следует найти длину наибольшей возрастающей подпоследовательности (НВП) для последовательности x₀, x₁, …, x_n-1.

Объявим массив lis, где lis[i] содержит длину НВП, которую можно выделить среди чисел x₀, x₁, …, x_i, и которая обязательно заканчивается элементом x_i. Если массив x содержит n чисел, то ответом задачи будет наибольшее среди чисел lis₀, …, lis_n-1. Значение lis₀ положим равным 1: НВП для последовательности из одного элемента равна этому самому элементу. Следующие значения массива lis вычисляются согласно соотношению:

Элемент x_i может продолжить только те НВП, которые заканчиваются элементом x_j, для которого j < i и x_j < x_i.

Решение за O(n log₂n). После обработки i элементов массива x хвост массива lis (ячейки от lis_k до lis_len-1 для некоторого k) содержит хвост наибольшей возрастающей подпоследовательности, которую можно выделить среди чисел x₀, x₁, …, x_i. При этом хвост этой НВП будет лексикографически наименьшим, а значение len равно длине НВП для последовательности x₀, x₁, …, x_i.

При обработке очередного элемента x_i вставим его в массив lis при помощи бинарного поиска. Если x_i больше значения lis_len-1, то элемент x_i увеличивает на единицу длину НВП, поэтому устанавливаем lis_len = x_i и увеличиваем len на 1. Если lis_k < x_i £ lis_k+1, то заменяем lis_k+1 на x_i. Эта операция не увеличивает длину НВП, но может лексикографически уменьшить хвост НВП.

После обработки всех элементов массива х значение len содержит длину НВП.

Пример

Для заданной в примере последовательности НВП может быть {3, 5, 6} или {3, 5, 28}. Длина НВП равна 3.

Рассмотрим следующий массив

Промоделируем на нем работу алгоритма. В каждой новой строке приведем состояние массива после очередной итерации.

Значение len = 5, следовательно длина НВП равна 5. Ею, например, может быть следующая последовательность:

Реализация алгоритма

Входную последовательность храним в массиве x. Объявим вспомогательный массив lis.

#define MAX 1001

int x[MAX], lis[MAX];

Основная часть программы. Читаем входную последовательность.

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&x[i]);

Проводим n итераций алгоритма.

for (len = i = 0; i < n; i++)

{

pos = lower_bound(lis,lis+len,x[i]) - lis;

if (pos < len) lis[pos] = x[i]; else lis[len++] = x[i];

}

Выводим длину НВП.

printf("%d\n",len);

Реализация алгоритма – STL vector

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> x, lis;

int i, n, len, pos;

int main(void)

{

scanf("%d", &n);

x.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &x[i]);

for (i = 0; i < n; i++)

{

pos = lower_bound(lis.begin(), lis.end(), x[i]) - lis.begin();

if (pos < lis.size()) lis[pos] = x[i]; else lis.push_back(x[i]);

}

printf("%d\n", lis.size());

return 0;

}

Реализация алгоритма – O(n²)

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> x, lis;

int i, j, n, res;

int main(void)

{

scanf("%d", &n);

x.resize(n); lis.resize(n);

for (i = 0; i < n; i++)

{

scanf("%d", &x[i]);

lis[i] = 1;

}

for (i = 0; i < n; i++)

for (j = 0; j < i; j++)

if (x[j] < x[i]) lis[i] = max(lis[i], 1 + lis[j]);

res = *max_element(lis.begin(), lis.end());

printf("%d\n", res);

return 0;

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int x[] = new int[n];

for (int i = 0; i < n; i++)

x[i] = con.nextInt();

int lis[] = new int[n];

int len = 0;

for (int i = 0; i < n; i++)

{

int pos = Arrays.binarySearch(lis, 0, len, x[i]);

if(pos < 0) pos = - (pos + 1);

lis[pos] = x[i];

if(pos == len) len++;

}

System.out.println(len);

con.close();

}

}