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

Question

При заданной входной последовательности наилучший способ найти самую длинную (не обязательно непрерывную) неубывающую подпоследовательность.

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 # sequence

1, 9, 13, 15 # non-decreasing subsequence

0, 2, 6, 9, 13, 15 # longest non-deceasing subsequence (not unique)

Я ищу лучший алгоритм. Если есть код, Python будет хорошо, но все в порядке.

Answer 1

Я только что наткнулся на эту проблему и придумал реализацию Python 3:

def subsequence(seq):
    if not seq:
        return seq

    M = [None] * len(seq)    # offset by 1 (j -> j-1)
    P = [None] * len(seq)

    # Since we have at least one element in our list, we can start by 
    # knowing that the there's at least an increasing subsequence of length one:
    # the first element.
    L = 1
    M[0] = 0

    # Looping over the sequence starting from the second element
    for i in range(1, len(seq)):
        # Binary search: we want the largest j <= L
        #  such that seq[M[j]] < seq[i] (default j = 0),
        #  hence we want the lower bound at the end of the search process.
        lower = 0
        upper = L

        # Since the binary search will not look at the upper bound value,
        # we'll have to check that manually
        if seq[M[upper-1]] < seq[i]:
            j = upper

        else:
            # actual binary search loop
            while upper - lower > 1:
                mid = (upper + lower) // 2
                if seq[M[mid-1]] < seq[i]:
                    lower = mid
                else:
                    upper = mid

            j = lower    # this will also set the default value to 0

        P[i] = M[j-1]

        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j+1)

    # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...]
    result = []
    pos = M[L-1]
    for _ in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return result[::-1]    # reversing

Поскольку мне потребовалось некоторое время, чтобы понять, как работает алгоритм, я был немного многословен с комментариями, и яТакже добавлю краткое объяснение:

• seq - это входная последовательность.
• L - это число: оно обновляется при цикле по последовательности и помечаетдлина самой длинной нарастающей подпоследовательности, найденной до этого момента.
• M - список.M[j-1] будет указывать на индекс seq, который содержит наименьшее значение, которое можно использовать (в конце) для построения возрастающей подпоследовательности длины j.
• P - это список.P[i] будет указывать на M[j], где i - индекс seq.В нескольких словах он говорит, какой из предыдущих элементов подпоследовательности является предыдущим.P используется для построения результата в конце.

Как работает алгоритм:

1. Обрабатывает особый случай пустой последовательности.
2. Начните с подпоследовательности из 1 элемента.
3. Цикл по входной последовательности с индексом i.
4. При бинарном поиске найдите j, в котором seq[M[j] будет <чем seq[i].
5. Обновление P, M и L.
6. Отслеживание результата и возврат его в обратном порядке.

Примечание: Единственными отличиями алгоритма википедии являются смещение 1 в списке M и то, что X здесь называется seq.Я также проверил его с помощью слегка улучшенной версии модульного теста, показанной в Эрике Густавсоне , и он прошел все тесты.

---

Пример:

seq = [30, 10, 20, 50, 40, 80, 60]

       0    1   2   3   4   5   6   <-- indexes

В конце у нас будет:

M = [1, 2, 4, 6, None, None, None]
P = [None, None, 1, 2, 2, 4, 4]
result = [10, 20, 40, 60]

Как вы увидите, P довольно просто.Мы должны смотреть на это с конца, поэтому он говорит, что до 60 есть 40, до 80 есть 40, до 40 есть 20, до 50 есть 20 и до20 есть 10, стоп.

Сложная часть на M.В начале M было [0, None, None, ...], так как последний элемент подпоследовательности длины 1 (следовательно, позиция 0 в M) имел индекс 0: 30.

В этот момент мы начнем цикл seq и посмотрим 10, поскольку 10 равно <, чем 30, M будет обновлено:

if j == L or seq[i] < seq[M[j]]:
    M[j] = i

Так что теперь M выглядит так: [1, None, None, ...].Это хорошо, потому что 10 имеет больше возможностей для создания более длинной подпоследовательности.(Новый 1 - это индекс 10)

Теперь очередь за 20.С 10 и 20 мы имеем подпоследовательность длины 2 (индекс 1 в M), поэтому M будет: [1, 2, None, ...].(Новые 2 - это индекс 20)

Теперь очередь за 50.50 не будет частью какой-либо подпоследовательности, поэтому ничего не меняется.

Теперь очередь за 40.С 10, 20 и 40 у нас есть подпункт длины 3 (индекс 2 в M, поэтому M будет: [1, 2, 4, None, ...]. (Новый 4 - это индекс 40)

И так далее ...

Для полного просмотра кода вы можете скопировать и вставить его здесь :)

Answer 2

Вот как просто найти самую длинную увеличивающуюся / убывающую подпоследовательность в Mathematica:

 LIS[list_] := LongestCommonSequence[Sort[list], list];
 input={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
 LIS[input]
 -1*LIS[-1*input]

Выход:

{0, 2, 6, 9, 11, 15}
{12, 10, 9, 5, 3}

Mathematica также имеет LongestIncreasingSubsequence функцию в Combinatorica` Библиотека.Если у вас нет Mathematica, вы можете запросить решение WolframAlpha .

C ++ O (nlogn)

Существует также решение O (nlogn), основанное на некоторыхнаблюдения.Пусть Ai, j будет наименьшим возможным хвостом из всех возрастающих подпоследовательностей длины j с использованием элементов a ₁ , a ₂ , ..., a _i .Обратите внимание, что для любого конкретного i, A _{i, 1} , A _{i, 2} , ..., A _{i, j} .Это говорит о том, что если нам нужна самая длинная подпоследовательность, которая заканчивается на ai + 1, нам нужно только искать aj, такой что Ai, j 1 , a ₂ , ..., a _n .

Реализация C ++ (алгоритм O (nlogn))

#include <vector>
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
  vector<int> p(a.size());
  int u, v;

  if (a.empty()) return;

  b.push_back(0);

  for (size_t i = 1; i < a.size(); i++) {
      if (a[b.back()] < a[i]) {
          p[i] = b.back();
          b.push_back(i);
          continue;
      }

      for (u = 0, v = b.size()-1; u < v;) {
          int c = (u + v) / 2;
          if (a[b[c]] < a[i]) u=c+1; else v=c;
      }

      if (a[i] < a[b[u]]) {
          if (u > 0) p[i] = b[u-1];
          b[u] = i;
      }   
  }

  for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}

/* Example of usage: */
#include <cstdio>
int main()
{
  int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
  vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
  vector<int> lis;
        find_lis(seq, lis);

  for (size_t i = 0; i < lis.size(); i++)
      printf("%d ", seq[lis[i]]);
        printf("\n");    

  return 0;
}

Источник: ссылка

Некоторое время назад я переписал реализацию C ++ для Java и могу подтвердить, что она работает.Векторной альтернативой в python является List.Но если вы хотите проверить это самостоятельно, вот ссылка для онлайн-компилятора с загруженной примером реализации: ссылка

Пример данных: { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 } и ответ: 1 3 4 5 6 7.

Answer 3

Вот довольно общее решение, которое:

• работает за O(n log n) время,
• обрабатывает увеличивающиеся, неубывающие, убывающие и не увеличивающиеся подпоследовательности,
• работает с любыми объектами последовательности, включая list, numpy.array, str и более,
• поддерживает списки объектов и пользовательские методы сравнения с помощью параметра key, который работает так же, как и во встроенной функции sorted,
• может возвращать элементы подпоследовательности или их индексы.

код:

from bisect import bisect_left, bisect_right
from functools import cmp_to_key

def longest_subsequence(seq, mode='strictly', order='increasing',
                        key=None, index=False):

  bisect = bisect_left if mode.startswith('strict') else bisect_right

  # compute keys for comparison just once
  rank = seq if key is None else map(key, seq)
  if order == 'decreasing':
    rank = map(cmp_to_key(lambda x,y: 1 if x<y else 0 if x==y else -1), rank)
  rank = list(rank)

  if not rank: return []

  lastoflength = [0] # end position of subsequence with given length
  predecessor = [None] # penultimate element of l.i.s. ending at given position

  for i in range(1, len(seq)):
    # seq[i] can extend a subsequence that ends with a lesser (or equal) element
    j = bisect([rank[k] for k in lastoflength], rank[i])
    # update existing subsequence of length j or extend the longest
    try: lastoflength[j] = i
    except: lastoflength.append(i)
    # remember element before seq[i] in the subsequence
    predecessor.append(lastoflength[j-1] if j > 0 else None)

  # trace indices [p^n(i), ..., p(p(i)), p(i), i], where n=len(lastoflength)-1
  def trace(i):
    if i is not None:
      yield from trace(predecessor[i])
      yield i
  indices = trace(lastoflength[-1])

  return list(indices) if index else [seq[i] for i in indices]

Я написал строку документации для функции, которую не вставил выше, чтобы показать код:

"""
Return the longest increasing subsequence of `seq`.

Parameters
----------
seq : sequence object
  Can be any sequence, like `str`, `list`, `numpy.array`.
mode : {'strict', 'strictly', 'weak', 'weakly'}, optional
  If set to 'strict', the subsequence will contain unique elements.
  Using 'weak' an element can be repeated many times.
  Modes ending in -ly serve as a convenience to use with `order` parameter,
  because `longest_sequence(seq, 'weakly', 'increasing')` reads better.
  The default is 'strict'.
order : {'increasing', 'decreasing'}, optional
  By default return the longest increasing subsequence, but it is possible
  to return the longest decreasing sequence as well.
key : function, optional
  Specifies a function of one argument that is used to extract a comparison
  key from each list element (e.g., `str.lower`, `lambda x: x[0]`).
  The default value is `None` (compare the elements directly).
index : bool, optional
  If set to `True`, return the indices of the subsequence, otherwise return
  the elements. Default is `False`.

Returns
-------
elements : list, optional
  A `list` of elements of the longest subsequence.
  Returned by default and when `index` is set to `False`.
indices : list, optional
  A `list` of indices pointing to elements in the longest subsequence.
  Returned when `index` is set to `True`.
"""

Некоторые примеры:

>>> seq = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

>>> longest_subsequence(seq)
[0, 2, 6, 9, 11, 15]

>>> longest_subsequence(seq, order='decreasing')
[12, 10, 9, 5, 3]

>>> txt = ("Given an input sequence, what is the best way to find the longest"
               " (not necessarily continuous) non-decreasing subsequence.")

>>> ''.join(longest_subsequence(txt))
' ,abdegilnorsu'

>>> ''.join(longest_subsequence(txt, 'weak'))
'              ceilnnnnrsssu'

>>> ''.join(longest_subsequence(txt, 'weakly', 'decreasing'))
'vuutttttttssronnnnngeee.'

>>> dates = [
...   ('2015-02-03', 'name1'),
...   ('2015-02-04', 'nameg'),
...   ('2015-02-04', 'name5'),
...   ('2015-02-05', 'nameh'),
...   ('1929-03-12', 'name4'),
...   ('2023-07-01', 'name7'),
...   ('2015-02-07', 'name0'),
...   ('2015-02-08', 'nameh'),
...   ('2015-02-15', 'namex'),
...   ('2015-02-09', 'namew'),
...   ('1980-12-23', 'name2'),
...   ('2015-02-12', 'namen'),
...   ('2015-02-13', 'named'),
... ]

>>> longest_subsequence(dates, 'weak')

[('2015-02-03', 'name1'),
 ('2015-02-04', 'name5'),
 ('2015-02-05', 'nameh'),
 ('2015-02-07', 'name0'),
 ('2015-02-08', 'nameh'),
 ('2015-02-09', 'namew'),
 ('2015-02-12', 'namen'),
 ('2015-02-13', 'named')]

>>> from operator import itemgetter

>>> longest_subsequence(dates, 'weak', key=itemgetter(0))

[('2015-02-03', 'name1'),
 ('2015-02-04', 'nameg'),
 ('2015-02-04', 'name5'),
 ('2015-02-05', 'nameh'),
 ('2015-02-07', 'name0'),
 ('2015-02-08', 'nameh'),
 ('2015-02-09', 'namew'),
 ('2015-02-12', 'namen'),
 ('2015-02-13', 'named')]

>>> indices = set(longest_subsequence(dates, key=itemgetter(0), index=True))

>>> [e for i,e in enumerate(dates) if i not in indices]

[('2015-02-04', 'nameg'),
 ('1929-03-12', 'name4'),
 ('2023-07-01', 'name7'),
 ('2015-02-15', 'namex'),
 ('1980-12-23', 'name2')]

Этот ответ был частично вдохновлен вопросом на Code Review и частично вопросом о значениях "out of sequence" .

Answer 4

Вот некоторый код на python с тестами, который реализует алгоритм, работающий в O (n * log (n)). Я нашел это на странице обсуждения в Википедии о самой длинной подпоследовательности .

import unittest


def LongestIncreasingSubsequence(X):
    """
    Find and return longest increasing subsequence of S.
    If multiple increasing subsequences exist, the one that ends
    with the smallest value is preferred, and if multiple
    occurrences of that value can end the sequence, then the
    earliest occurrence is preferred.
    """
    n = len(X)
    X = [None] + X  # Pad sequence so that it starts at X[1]
    M = [None]*(n+1)  # Allocate arrays for M and P
    P = [None]*(n+1)
    L = 0
    for i in range(1,n+1):
        if L == 0 or X[M[1]] >= X[i]:
            # there is no j s.t. X[M[j]] < X[i]]
            j = 0
        else:
            # binary search for the largest j s.t. X[M[j]] < X[i]]
            lo = 1      # largest value known to be <= j
            hi = L+1    # smallest value known to be > j
            while lo < hi - 1:
                mid = (lo + hi)//2
                if X[M[mid]] < X[i]:
                    lo = mid
                else:
                    hi = mid
            j = lo

        P[i] = M[j]
        if j == L or X[i] < X[M[j+1]]:
            M[j+1] = i
            L = max(L,j+1)

    # Backtrack to find the optimal sequence in reverse order
    output = []
    pos = M[L]
    while L > 0:
        output.append(X[pos])
        pos = P[pos]
        L -= 1

    output.reverse()
    return output

# Try small lists and check that the correct subsequences are generated.

class LISTest(unittest.TestCase):
    def testLIS(self):
        self.assertEqual(LongestIncreasingSubsequence([]),[])
        self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1])
        self.assertEqual(LongestIncreasingSubsequence(range(10)),range(10))
        self.assertEqual(LongestIncreasingSubsequence(\
            [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]), [1,2,3,5,8,9])

unittest.main()

Answer 5

Вот код и объяснение с Java, возможно, я скоро добавлю для python.

arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

1. list = {0} - Инициализировать список пустым набором
2. list = {0,8} - Новая самая большая LIS
3. list = {0, 4} - Изменено 8 на 4
4. list = {0, 4, 12} - Новая самая большая LIS
5. list = {0, 2, 12} - изменено 4 на 2
6. list = {0, 2, 10} - изменено 12 на 10
7. list = {0,2, 6} - изменено 10 на 6
8. список = {0, 2, 6, 14} - новый наибольший LIS
9. список = {0, 1, 6, 14} - изменено 2на 1
10. список = {0, 1, 6, 9} - изменен с 14 на 9
11. список = {0, 1, 5, 9} - изменен с 6 на 5
12. list = {0, 1, 6, 9, 13} - изменен с 3 на 2
13. list = {0, 1, 3, 9, 11} - новый по величине список LIS
14. = {0, 1, 3, 9, 11} - изменен с 9 на 5
15. list = {0, 1, 3, 7, 11} - новый по величине LIS
16. list = {0, 1, 3, 7, 11, 15} - Новый по величине LIS

Таким образом, длина LIS равна 6 (размер списка).

import java.util.ArrayList;
import java.util.List;


public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
        increasingSubsequenceValues(arr);
    }

    public static void increasingSubsequenceValues(int[] seq) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < seq.length; i++) {
            int j = 0;
            boolean elementUpdate = false;
            for (; j < list.size(); j++) {
                if (list.get(j) > seq[i]) {
                    list.add(j, seq[i]);
                    list.remove(j + 1);
                    elementUpdate = true;
                    break;
                }
            }
            if (!elementUpdate) {
                list.add(j, seq[i]);
            }
        }
        System.out.println("Longest Increasing Subsequence" + list);
    }


}

Выводдля вышеуказанного кода: самая длинная возрастающая подпоследовательность [0, 1, 3, 7, 11, 15]

Answer 6

    int[] a = {1,3,2,4,5,4,6,7};
    StringBuilder s1 = new StringBuilder();
    for(int i : a){
     s1.append(i);
    }       
    StringBuilder s2 = new StringBuilder();
    int count = findSubstring(s1.toString(), s2);       
    System.out.println(s2.reverse());

public static int findSubstring(String str1, StringBuilder s2){     
    StringBuilder s1 = new StringBuilder(str1);
    if(s1.length() == 0){
        return 0;
    }
    if(s2.length() == 0){
        s2.append(s1.charAt(s1.length()-1));
        findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2);           
    } else if(s1.charAt(s1.length()-1) < s2.charAt(s2.length()-1)){ 
        char c = s1.charAt(s1.length()-1);
        return 1 + findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2.append(c));
    }
    else{
        char c = s1.charAt(s1.length()-1);
        StringBuilder s3 = new StringBuilder();
        for(int i=0; i < s2.length(); i++){
            if(s2.charAt(i) > c){
                s3.append(s2.charAt(i));
            }
        }
        s3.append(c);
        return Math.max(findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s2), 
                findSubstring(s1.deleteCharAt(s1.length()-1).toString(), s3));
    }       
    return 0;
}

Answer 7

Вот мое C ++ решение проблемы. Решение проще, чем все представленные здесь, и оно быстрое: N*log(N) алгоритмическая сложность времени. Я отправил решение на Leetcode, оно работает 4 мс, быстрее, чем 100% представленных решений C ++.

Идея (на мой взгляд) ясна: пройти заданный массив чисел слева направо. Поддерживать дополнительно массив чисел (seq в моем коде), который содержит возрастающую подпоследовательность. Когда взятое число больше всех чисел, содержащихся в подпоследовательности, поместите его в конец seq и увеличьте счетчик длины подпоследовательности на 1. Когда число меньше наибольшего числа в подпоследовательности, поместите его в любом случае в seq, в том месте, где она хранится, подпоследовательность сортируется путем замены некоторого существующего числа. Подпоследовательность инициализируется длиной массива исходных чисел и начальным значением -inf, что означает наименьшее целое число в данной ОС.

Пример:

числа = {10, 9, 2, 5, 3, 7, 101, 18}

seq = {-inf, -inf, -inf, -inf, -inf, -inf, -inf}

вот как меняется последовательность, когда мы пересекаем числа слева направо:

 seq = {10, -inf, -inf, -inf, -inf, -inf, -inf}
 seq = {9, -inf, -inf, -inf, -inf, -inf, -inf}
 seq = {2, -inf, -inf, -inf, -inf, -inf, -inf}
 seq = {2, 5, -inf, -inf, -inf, -inf, -inf}
 seq = {2, 3, -inf, -inf, -inf, -inf, -inf}
 seq = {2, 3, 7, -inf, -inf, -inf, -inf}
 seq = {2, 3, 7, 101, -inf, -inf, -inf}
 seq = {2, 3, 7, 18, -inf, -inf, -inf}

Самая длинная возрастающая подпоследовательность для массива имеет длину 4.

Вот код:

int longestIncreasingSubsequence(const vector<int> &numbers){
    if (numbers.size() < 2)
        return numbers.size();
    vector<int>seq(numbers.size(), numeric_limits<int>::min());
    seq[0] = numbers[0];
    int len = 1;
    vector<int>::iterator end = next(seq.begin());
    for (size_t i = 1; i < numbers.size(); i++) {
        auto pos = std::lower_bound(seq.begin(), end, numbers[i]);
        if (pos == end) {
            *end = numbers[i];
            end = next(end);
            len++;
        }
        else
            *pos = numbers[i];
    }
    return len;
}

Ну, пока все хорошо, но как мы узнаем, что алгоритм вычисляет длину самой длинной (или одной из самых длинных, здесь может быть несколько подпоследовательностей одинакового размера) подпоследовательности? Вот мое доказательство:

Предположим, что алгоритм не вычисляет длину самой длинной подпоследовательности. Тогда в исходной последовательности должно существовать число, такое, что алгоритм пропущен, и это сделает подпоследовательность более длинной. Скажем, для подпоследовательности x ₁ , x ₂ , ..., x _n существует такое число y, что x _k k + 1 , 1 <= k <= n. Чтобы внести вклад в подпоследовательность, y должен находиться в исходной последовательности между x <sub>k и x _{k + 1} . Но тогда мы имеем противоречие: когда алгоритм пересекает исходную последовательность слева направо, каждый раз, когда он встречает число, большее, чем любое число в текущей подпоследовательности, он расширяет подпоследовательность на 1. К тому времени, когда алгоритм встретит такое число y, подпоследовательность будет иметь длину k и содержать числа x ₁ , x ₂ , ..., x _k . Поскольку x _k 1 или когда y является наибольшим номером подпоследовательности и расположен справа от x _n . Вывод: такого числа у не существует и алгоритм вычисляет самую длинную возрастающую подпоследовательность. Я надеюсь, что это имеет смысл.

В заключительном утверждении я хотел бы упомянуть, что алгоритм может быть легко обобщен для вычисления самой длинной убывающей подпоследовательности для любых типов данных, элементы которых можно упорядочить. Идея та же, вот код:

template<typename T, typename cmp = std::less<T>>
size_t longestSubsequence(const vector<T> &elements)
{
    if (elements.size() < 2)
        return elements.size();
    vector<T>seq(elements.size(), T());
    seq[0] = elements[0];
    size_t len = 1;
    auto end = next(seq.begin());
    for (size_t i = 1; i < elements.size(); i++) {
        auto pos = std::lower_bound(seq.begin(), end, elements[i], cmp());
        if (pos == end) {
            *end = elements[i];
            end = next(end);
            len++;
        }
        else
            *pos = elements[i];
    }
    return len;
}

Примеры использования:

int main()
{
    vector<int> nums = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
    size_t l = longestSubsequence<int>(nums); // l == 6 , longest increasing subsequence

    nums = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
    l = longestSubsequence<int, std::greater<int>>(nums); // l == 5, longest decreasing subsequence

    vector<string> vstr = {"b", "a", "d", "bc", "a"};
    l = longestSubsequence<string>(vstr); // l == 2, increasing


    vstr = { "b", "a", "d", "bc", "a" };
    l = longestSubsequence<string, std::greater<string>>(vstr); // l == 3, decreasing

} 

Answer 8

В коде есть несколько ответов, но я нашел их немного сложными для понимания, поэтому здесь приводится объяснение общей идеи, оставляя без внимания все оптимизации.Позже я вернусь к оптимизации.

Мы будем использовать последовательность 2, 8, 4, 12, 3, 10, и, чтобы было легче следовать, нам потребуется, чтобы входная последовательность не была пустой ине включать один и тот же номер более одного раза.

Мы проходим последовательность по порядку.

При этом мы поддерживаем набор последовательностей, лучшие последовательности, которые мы до сих пор нашли для каждой длины.После того, как мы находим первую последовательность длины 1, которая является первым элементом входной последовательности, мы гарантированно получим набор последовательностей для каждой возможной длины от 1 до самой длинной, которую мы до сих пор нашли.Это очевидно, потому что если у нас есть последовательность длиной 3, то первые 2 элемента этой последовательности являются последовательностью длины 2.

Итак, мы начинаем с того, что первый элемент представляет собой последовательность длины 1, и нашset выглядит как

 1: 2

Мы берем следующий элемент последовательности (8) и ищем самую длинную последовательность, к которой мы можем добавить его.Это последовательность 1, поэтому мы получаем

1: 2
2: 2 8

. Мы берем следующий элемент последовательности (4) и ищем самую длинную последовательность, к которой мы можем добавить его.Самая длинная последовательность, к которой мы можем добавить это длина 1 (которая просто 2). Вот то, что я нашел для хитрой (или, по крайней мере, неочевидной) части. Поскольку мы не смогли добавить ее в конец последовательности длины 2 (2 8), что означает это должен быть лучший выбор, чтобы закончить длину 2 кандидата .Если бы элемент был больше 8, он бы привязался к последовательности длины 2 и дал бы нам новую последовательность длины 3.Итак, мы знаем, что оно меньше 8, и поэтому заменим 8 на 4.

С точки зрения алгоритма, мы говорим, что независимо от того, какую самую длинную последовательность мы можем привязать к элементу, эта последовательность плюс этот элемент являетсялучший кандидат на последовательность результирующей длины. Обратите внимание, что каждый элемент, который мы обрабатываем, должен где-то принадлежать (потому что мы исключили повторяющиеся числа во входных данных).Если он меньше элемента длины 1, это новая длина 1, в противном случае он идет в конце некоторой существующей последовательности. Здесь последовательность длины 1 плюс элемент 4 становится новой последовательностью длины 2, и мыимеем:

1: 2
2: 2 4 (replaces 2 8)

Следующий элемент 12 дает нам последовательность длины 3, и мы имеем

1: 2
2: 2 4
3: 2 4 12

Следующий элемент 3 дает нам лучшую последовательность длины 2:

1: 2
2: 2 3 (replaces 2 4)
3: 2 4 12

Обратите внимание, что мы не можем изменить последовательность длины 3 (подставляя 3 вместо 4), потому что они не встречались в указанном порядке во входной последовательности.Следующий элемент, 10, заботится об этом.Поскольку лучшее, что мы можем сделать с 10, это добавить его к 2 3, он становится новым списком длины 3:

1: 2
2: 2 3
3: 2 3 10 (replaces 2 4 12)

Обратите внимание, что с точки зрения алгоритма нам действительно все равно, что получитсяперед последним элементом в любой из наших последовательностей-кандидатов, но, конечно, мы должны отслеживать, чтобы в конце мы могли вывести полную последовательность.

Мы продолжаем обрабатывать входные элементы так: просто прикрепите каждый из них к самой длинной последовательности, которую мы можем, и сделайте эту новую последовательность-кандидат для полученной длины, потому что она гарантированно не будет хуже существующей последовательности этогодлина.В конце мы выводим самую длинную последовательность, которую мы нашли.

Оптимизации

Одна оптимизация заключается в том, что нам не нужно хранить всю последовательность каждой длины.Для этого потребовалось бы место O (n ^ 2).По большей части, мы можем просто сохранить последний элемент каждой последовательности, так как это все, с чем мы когда-либо сравнивали.(Я немного позже пойму, почему этого недостаточно). Посмотрим, сможете ли вы выяснить, почему, прежде чем я это сделаю.)

Допустим, мы будем хранить наш набор последовательностей в виде массива M, где M[x] содержит последний элемент последовательности длиной x. Если вы подумаете об этом, вы поймете, что элементы M сами в порядке возрастания: они отсортированы. Если бы M[x+1] было меньше M[x], оно заменило бы M[x].

Поскольку M отсортировано, следующая оптимизация идет к чему-то, что я полностью затмил выше: как нам найти последовательность, к которой можно добавить? Итак, поскольку M отсортировано, мы можем просто выполнить бинарный поиск, чтобы найти самое большое M[x] меньше, чем добавляемый элемент. Это последовательность, к которой мы добавляем.

Это здорово, если все, что мы хотим сделать, это найти длину самой длинной последовательности. Однако M недостаточно для восстановления самой последовательности. Помните, однажды наш сет выглядел так:

1: 0
2: 0 2
3: 0 4 12

Мы не можем просто вывести M в виде последовательности. Нам нужно больше информации, чтобы иметь возможность восстановить последовательность. Для этого мы делаем еще 2 изменения . Сначала , мы сохраняем входную последовательность в массиве seq и вместо того, чтобы хранить значение элемента в M[x], мы сохраняем индекс элемента в seq, поэтому значение равно seq[M[x]].

Мы делаем это так, чтобы мы могли вести запись всей последовательности, связывая подпоследовательности. Как вы видели в начале, каждая последовательность создается путем добавления одного элемента в конец уже существующей последовательности. Итак, секунда , мы сохраняем другой массив P, в котором хранится индекс (в seq) последнего элемента последовательности, к которой мы добавляем. Чтобы сделать его цепочечным, поскольку то, что мы храним в P, является индексом seq, мы должны сами индексировать P по индексу seq.

Это работает так, что при обработке элемента i из seq мы находим, к какой последовательности мы добавляем. Помните, мы собираемся прикрепить seq[i] к последовательности длиной x, чтобы создать новую последовательность длиной x+1 для некоторого x, и мы храним i, а не seq[i] в M[x+1] , Позже, когда мы обнаружим, что x+1 является самой большой возможной длиной, мы собираемся восстановить последовательность, но единственная отправная точка, которую мы имеем, это M[x+1].

Мы устанавливаем M[x+1] = i и P[i] = M[x] (что идентично P[M[x+1]] = M[x]), то есть для каждого добавляемого нами элемента i мы сохраняем i как последний элемент в самая длинная цепочка, которую мы можем, и мы храним индекс последнего элемента цепочки, который мы расширяем, в P[i]. Итак имеем:

last element: seq[M[x]]
 before that: seq[P[M[x]]]
 before that: seq[P[P[M[x]]]]
 etc...

И теперь мы закончили. Если вы хотите сравнить это с реальным кодом, вы можете посмотреть другие примеры . Основное отличие состоит в том, что они используют j вместо x, могут хранить список длины j в M[j-1] вместо M[j], чтобы не тратить пространство на M[0], и могут вызывать входную последовательность X вместо seq.

Answer 9

Вот более компактная, но все же эффективная реализация Python:

def longest_increasing_subsequence_indices(seq):
    from bisect import bisect_right

    if len(seq) == 0:
        return seq

    # m[j] in iteration i is the last index of the increasing subsequence of seq[:i]
    # that ends with the lowest possible value while having length j
    m = [None] * len(seq)
    predecessor = [None] * len(seq)
    best_len = 0

    for i, item in enumerate(seq):
        j = bisect_right([seq[k] for k in m[:best_len]], item)
        m[j] = i
        predecessor[i] = m[j-1] if j > 0 else None
        best_len = max(best_len, j+1)

    result = []
    i = m[best_len-1]
    while i is not None:
        result.append(i)
        i = predecessor[i]
    result.reverse()
    return result

def longest_increasing_subsequence(seq):
    return [seq[i] for i in longest_increasing_subsequence_indices(seq)]

Answer 10

вот компактная реализация, использующая "enumerate"

def lis(l):

# we will create a list of lists where each sub-list contains
# the longest increasing subsequence ending at this index
lis = [[e] for e in l]
# start with just the elements of l as contents of the sub-lists

# iterate over (index,value) of l
for i, e in enumerate(l):
    # (index,value) tuples for elements b where b<e and a<i
    lower_tuples = filter(lambda (a,b): b<e, enumerate(l[:i]))
    # if no such items, nothing to do
    if not lower_tuples: continue
    # keep the lis-es of such items
    lowerlises = [lis[a] for a,b in  lower_tuples ]
    # choose the longest one of those and add
    # to the current element's lis
    lis[i] = max(lowerlises, key=len) + [e]

# retrun the longest of lis-es
return max(lis, key=len)