Учитывая входную последовательность, наилучший способ найти самую длинную (не обязательно непрерывную) неубывающую подпоследовательность.
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 будет приятным, но все в порядке.
Я просто наткнулся на эту проблему и придумал реализацию 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 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 используется для построения результата в конце.Как работает алгоритм:
i.j, которые позволяют seq[M[j] быть < чем seq[i].P, M и L Примечание. Единственными отличиями в алгоритме википедии являются смещение 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)
И так далее...
Для полной прогулки по коду вы можете скопировать и вставить его здесь :)
Вот как просто найти самую длинную возрастающую/уменьшающуюся подпоследовательность в 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.
Решение С++ O (nlogn)
Также существует решение O (nlogn), основанное на некоторых наблюдения. Пусть Ai, j - наименьший возможный хвост из всех увеличивающихся подпоследовательности длины j, используя элементы a 1, a 2,..., a i. Обратите внимание, что для любого конкретный i, A i, 1, A i, 2,..., A i, j. Это говорит о том, что если нам нужна самая длинная подпоследовательность заканчивается ai + 1, нам нужно только посмотреть для j j таких, что Ai, j < ai + 1 < знак равно Ai, j + 1 и длина будет j + 1. Заметим, что в этом случае Ai + 1, j + 1 будет равно ai + 1, а все Ai + 1, k будет равно Ai, k при k!= J + 1. Кроме того, существует не более одного разность между множеством Ai и set Ai + 1, что вызвано этим поиск. Так как А всегда упорядочено в возрастающий порядок и операция не меняет этот порядок, мы можем выполните двоичный поиск для каждого отдельного 1, 2,..., a n.
Реализация С++ (алгоритм 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; }
Источник: ссылка
Я недавно переписал реализацию С++ для Java и могу подтвердить, что она работает. Альтернативой вектора в python является List. Но если вы хотите проверить его самостоятельно, вот ссылка для онлайн-компилятора с загруженным примером реализации: ссылка
Примеры данных: { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }
и ответ: 1 3 4 5 6 7.
Вот довольно общее решение, которое:
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]
Я написал docstring для функции, которую я не вставлял выше, чтобы показать код:
"""
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')]
Этот ответ частично был вдохновлен вопросом в обзоре кода и частично вопросом, спрашивающим о "из последовательности" .
Вот некоторый код python с тестами, которые реализуют алгоритм, выполняющийся в O (n * log (n)). Я нашел это на странице wikipedia о самой длинной растущей подпоследовательности.
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()
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;
}
Вот код и объяснение с Java, возможно, я скоро добавлю для python.
arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Таким образом, длина 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]
Самый эффективный алгоритм для этого - O (NlogN), обозначенный здесь.
Еще один способ решить эту задачу - взять самую длинную общую подпоследовательность (LCS) исходного массива и отсортированную версию, которая принимает O ( N 2).
здесь реализована компактная реализация с использованием "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 lis
lis[i] = max(lowerlises, key=len) + [e]
# retrun the longest of lis-es
return max(lis, key=len)
Здесь более компактная, но все же эффективная реализация 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)]
В коде есть несколько ответов, но я нашел их немного сложными для понимания, поэтому здесь приводится объяснение общей идеи, оставляя без внимания все оптимизации. Я доберусь до оптимизации позже.
Мы будем использовать последовательность 2, 8, 4, 12, 3, 10, и, чтобы было легче следовать, нам потребуется, чтобы входная последовательность не была пустой и не включала одно и то же число более одного раза.
Проходим последовательность по порядку.
Как мы делаем, мы поддерживаем набор последовательностей, лучшие последовательности, которые мы до сих пор нашли для каждой длины. После того, как мы находим первую последовательность длины 1, которая является первым элементом входной последовательности, мы гарантированно получим набор последовательностей для каждой возможной длины от 1 до самой длинной, которую мы до сих пор нашли. Это очевидно, потому что если у нас есть последовательность длины 3, то первые 2 элемента этой последовательности являются последовательностью длины 2.
Итак, мы начинаем с первого элемента, представляющего собой последовательность длины 1, и наш набор выглядит следующим образом:
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.
Вот мое 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 1, x 2,..., x n существует такое число y, что x k & lt; у & lt; x k + 1, 1 & lt; = k & lt; = n. Чтобы внести вклад в подпоследовательность, y должен находиться в исходной последовательности между x k и x k + 1. Но тогда мы имеем противоречие: когда алгоритм пересекает исходную последовательность слева направо, каждый раз, когда он встречает число, большее, чем любое число в текущей подпоследовательности, он расширяет подпоследовательность на 1. К тому времени, когда алгоритм встретит такое число y, подпоследовательность будет иметь длину k и содержать числа x 1, x 2,..., x k. Потому что x k & lt; y, алгоритм расширит подпоследовательность на 1 и включит y в подпоследовательность. Та же логика применяется, когда у - наименьшее число подпоследовательности, расположенное слева от x 1 или когда у - наибольшее число подпоследовательности и расположенное справа от 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
}
def longest_sub_seq(arr):
main_arr = []
sub_arr = []
n = len(arr)
for ind in range(n):
if ind < n - 1 and arr[ind] <= arr[ind+1]:
sub_arr.append(arr[ind])
else:
sub_arr.append(arr[ind])
main_arr.append(sub_arr)
sub_arr = []
return max(main_arr, key=len)
a = [3, 10, 3, 11, 4, 5, 6, 7, 8, 12, 1, 2, 3]
print(longest_sub_seq(a)) # op: [4, 5, 6, 7, 8, 12]