Задача о наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 40: Строка 40:
 
Для восстановления ответа будем поддерживать заполнение двух массивов:<tex>pos</tex> и <tex>prev</tex>. В <tex>pos[i]</tex> будем хранить позицию <tex>d[i]</tex> в <tex>a[i]</tex>, а в <tex>prev[i]</tex> - позицию предыдущего элемента для <tex>a[i]</tex>.
 
Для восстановления ответа будем поддерживать заполнение двух массивов:<tex>pos</tex> и <tex>prev</tex>. В <tex>pos[i]</tex> будем хранить позицию <tex>d[i]</tex> в <tex>a[i]</tex>, а в <tex>prev[i]</tex> - позицию предыдущего элемента для <tex>a[i]</tex>.
 
<code>
 
<code>
  vector <int> Find(vector <int> a)
+
  vector<int> Find(vector<int> a)
{
+
    int n = a.size();
int d[maxN];
+
    int length = 0;  
int pos[maxN];//pos[i] - позиция d[i] в a[i]
+
    int d[n], pos[n], prev[n];
int prev[maxN];
+
    prev[0] = -1;
prev[0] = -1;
+
    d[0] = -INFINITY;
d[0] = -INF;
+
    for i = 1...n - 1
for i = 0...n
+
        d[i] = INFINITY;
    d[i] = INF;
+
    for i = 0...n - 1
for i = 0...n
+
        int j = binsearch(d[], a[i]);
    int j = binsearch(d, a[i]);//поиск первого числа, строго большего a[i]
+
        if d[j - 1] < a[i] and a[i] < d[j]
    if(d[j - 1] < a[i] && a[i] < d[j])
+
            d[j] = a[i];
          d[j] = a[i];
+
            pos[j] = i;
          pos[j] = i;
+
            prev[i] = pos[d[j - 1]];
          prev[i] = pos[d[j - 1]];//предок a[i] - позиция элемента d[j - 1] в исходном массиве a[i]
+
            length = max(length, j);
          size = max(size, j);
+
    vector<int> answer;
int it = size;
+
    int pos = length;
vector <int> answer;
+
    while pos != -INFINITY
while(it != -INF)
+
        answer.push_back(a[prev[pos]]);
    answer.push_back(a[prev[it]]);
+
        pos = a[prev[pos]];
    it = a[prev[it]];
+
    return answer;
return answer;
 
}
 
 
</code>
 
</code>
 
== Источники ==
 
== Источники ==

Версия 01:57, 3 декабря 2011

Дан массив из [math]n[/math] чисел: [math]a[0..n - 1][/math]. Требуется найти в этой последовательности строго возрастающую подпоследовательность наибольшей длины.

Определение:
Наибольшая возрастающая подпоследовательность (НВП) (англ. Longest increasing subsequence - LIS) строки [math] x [/math] длины [math] n [/math] - это последовательность [math] x[i_1] \lt x[i_2] \lt \dots \lt x[i_k] [/math] символов строки [math] x [/math] таких, что [math] i_1 \lt i_2 \lt \dots \lt i_k, 1 \le i_j \le n [/math], причем [math] k [/math] - наибольшее из возможных.

Решение за время O(N2)

Построим массив [math]d[/math], где [math]d[i][/math] [math]-[/math] это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом [math]i[/math]. Массив будем заполнять постепенно - сначала [math]d[0][/math], потом [math]d[1][/math] и т.д. Ответом на нашу задачу будет максимум из всех элементов массива [math]d[][/math]. Заполнение массива будет следующим: если [math]d[i] = 1[/math], то искомая последовательность состоит только из числа [math]a[i][/math]. Если [math]d[i] \gt 1[/math], то перед числом [math]a[i][/math] в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент [math]a[j](j = 0...i - 1)[/math], но такой, что [math]a[j] \lt a[i][/math]. Пусть на каком-то шаге нам надо посчитать очередное [math]d[i][/math]. Все элементы массива [math]d[][/math] до него уже посчитаны. Значит наше [math]d[i][/math] мы можем посчитать следующим образом: [math]d[i] = max(d[j][/math], для всех [math]j = 0...i - 1)[/math] при условии, что [math]a[j] \lt a[i][/math].

Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив [math]prev[0...n - 1][/math], где [math]prev[i][/math] будет означать индекс в массиве [math]a[][/math], при котором достигалось наибольшее значение [math]d[i][/math]. Для вывода ответа будем идти от элемента с максимальным значениям [math]d[i][/math] по его предкам.

vector<int> Find(vector<int> a)
    int n = a.size();//размер исходной последовательности
    vector<int> prev(n);
    vector<int> d(n);
    for i = 0...n - 1
        d[i] = 1;
        p[i] = -1;
        for j = 0...i - 1
            if a[j] < a[i]
                if d[j] + 1 > d[i]
                    d[i] = d[j] + 1;
                    prev[i] = j;
    int length = d[0], pos = 0;//length - длина наибольшей подпоследовательности, pos - последний символ наибольшей возрастающей подпоследовательности
    for i = 0...n - 1
        if d[i] > length
            length = d[i];
            pos = i;
    vector<int> answer;
    while pos != -1
        answer.push_back(a[pos]);
        pos = prev[pos];
    reverse(answer);
    return answer;    

Решение за O(NlogN)

Для более быстрого решения данной задачи построим следующую динамику: пусть [math]d[i](i = 0...n)[/math] - число, на которое оканчивается возрастающая последовательность длины [math]i[/math], а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что [math]d[0] = -[/math][math]\infty[/math], а все остальные элементы [math]d[i] =[/math] [math]\infty[/math]. Заметим два важных свойства этой динамики: [math]d[i - 1] \lt = d[i][/math], для всех [math]i = 1...n[/math]. А так же что каждый элемент [math]a[i][/math] обновляет максимум один элемент [math]d[j][/math]. Это означает, что при обработке очередного [math]a[i][/math], мы можем за [math] O(n\cdot\log n) [/math] c помощью двоичного поиска в массиве [math]d[][/math] найти первое число, которое строго больше текущего [math]a[i][/math] и обновить его. Для восстановления ответа будем поддерживать заполнение двух массивов:[math]pos[/math] и [math]prev[/math]. В [math]pos[i][/math] будем хранить позицию [math]d[i][/math] в [math]a[i][/math], а в [math]prev[i][/math] - позицию предыдущего элемента для [math]a[i][/math].

vector<int> Find(vector<int> a)
    int n = a.size();
    int length = 0; 
    int d[n], pos[n], prev[n];
    prev[0] = -1;
    d[0] = -INFINITY;
    for i = 1...n - 1 
        d[i] = INFINITY;
    for i = 0...n - 1
        int j = binsearch(d[], a[i]);
        if d[j - 1] < a[i] and a[i] < d[j]
            d[j] = a[i];
            pos[j] = i;
            prev[i] = pos[d[j - 1]];
            length = max(length, j);
    vector<int> answer;
    int pos = length;
    while pos != -INFINITY 
        answer.push_back(a[prev[pos]]);
        pos = a[prev[pos]];
    return answer;

Источники