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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
== Решение за время O(N<sup>2</sup>) ==
 
== Решение за время O(N<sup>2</sup>) ==
 
Построим массив <tex>d</tex>, где <tex>d[i]</tex> <tex>-</tex> это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом <tex>i</tex>. Массив будем заполнять постепенно - сначала <tex>d[0]</tex>, потом <tex>d[1]</tex> и т.д. Ответом на нашу задачу будет максимум из всех элементов массива <tex>d[]</tex>.
 
Построим массив <tex>d</tex>, где <tex>d[i]</tex> <tex>-</tex> это длина наибольшей возрастающей подпоследовательности, оканчивающейся в элементе, с индексом <tex>i</tex>. Массив будем заполнять постепенно - сначала <tex>d[0]</tex>, потом <tex>d[1]</tex> и т.д. Ответом на нашу задачу будет максимум из всех элементов массива <tex>d[]</tex>.
Заполнение массива будет следующим: если <tex>d[i] = 1</tex>, то искомая последовательность состоит только из числа <tex>a[i]</tex>. Если <tex>d[i] > 1</tex>, то перед числом <tex>a[i]</tex> в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент <tex>a[j](j = 0...i - 1)</tex>, но такой, что <tex>a[j] < a[i]</tex>. Пусть на каком-то шаге нам надо посчитать очередное <tex>d[i]</tex>. Все элементы массива <tex>d[]</tex> до него уже посчитаны. Значит наше <tex>d[i]</tex> мы можем посчитать следующим образом: <tex>d[i] = max(d[j]</tex>, для всех <tex>j = 0...i - 1)</tex> при условии, что <tex>a[j] < a[i]</tex>.
+
Заполнение массива будет следующим: если <tex>d[i] = 1</tex>, то искомая последовательность состоит только из числа <tex>a[i]</tex>. Если <tex>d[i] > 1</tex>, то перед числом <tex>a[i]</tex> в подпоследовательности стоит какое-то другое число. Переберем его: это может быть любой элемент <tex>a[j](j = 0...i - 1)</tex>, но такой, что <tex>a[j] < a[i]</tex>. Пусть на каком-то шаге нам надо посчитать очередное <tex>d[i]</tex>. Все элементы массива <tex>d[]</tex> до него уже посчитаны. Значит наше <tex>d[i]</tex> мы можем посчитать следующим образом: <tex>d[i] = 1 + max(d[j]</tex>, для всех <tex>j = 0...i - 1)</tex> при условии, что <tex>a[j] < a[i]</tex>.
  
 
Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив <tex>prev[0...n - 1]</tex>, где <tex>prev[i]</tex> будет означать индекс в массиве <tex>a[]</tex>, при котором достигалось наибольшее значение <tex>d[i]</tex>. Для вывода ответа будем идти от элемента с максимальным значениям <tex>d[i]</tex> по его предкам.
 
Пока что мы нашли лишь максимальную длину наибольшей возрастающей подпоследовательности, но саму ее мы вывести не можем. Для восстановления ответа заведем массив <tex>prev[0...n - 1]</tex>, где <tex>prev[i]</tex> будет означать индекс в массиве <tex>a[]</tex>, при котором достигалось наибольшее значение <tex>d[i]</tex>. Для вывода ответа будем идти от элемента с максимальным значениям <tex>d[i]</tex> по его предкам.
Строка 37: Строка 37:
 
== Решение за O(NlogN) ==
 
== Решение за O(NlogN) ==
 
Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> - число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -</tex><tex>\infty</tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.
 
Для более быстрого решения данной задачи построим следующую динамику: пусть <tex>d[i](i = 0...n)</tex> - число, на которое оканчивается возрастающая последовательность длины <tex>i</tex>, а если таких чисел несколько - то наименьшее из них. Изначально мы предполагаем, что <tex>d[0] = -</tex><tex>\infty</tex>, а все остальные элементы <tex>d[i] =</tex> <tex>\infty</tex>.
Заметим два важных свойства этой динамики: <tex>d[i - 1] <= d[i]</tex>, для всех <tex>i = 1...n</tex>. А так же что каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>. Это означает, что при обработке очередного <tex>a[i]</tex>, мы можем за <tex> O(n\cdot\log n) </tex> c помощью двоичного поиска в массиве <tex>d[]</tex> найти первое число, которое строго больше текущего <tex>a[i]</tex> и обновить его.
+
Заметим два важных свойства этой динамики: <tex>d[i - 1]</tex> <tex>\le</tex> <tex>d[i]</tex>, для всех <tex>i = 1...n</tex>. А так же что каждый элемент <tex>a[i]</tex> обновляет максимум один элемент <tex>d[j]</tex>. Это означает, что при обработке очередного <tex>a[i]</tex>, мы можем за <tex> O(n\cdot\log n) </tex> c помощью двоичного поиска в массиве <tex>d[]</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>.
 
Для восстановления ответа будем поддерживать заполнение двух массивов:<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>

Версия 06:29, 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] = 1 + 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][/math] [math]\le[/math] [math]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]];
    reverse(answer);
    return answer;

Источники