Как определить самую длинную возрастающую подпоследовательность с помощью динамического программирования?
У меня есть набор целых чисел. Я хочу найти самую длинную увеличивающуюся подпоследовательность этого набора, используя динамическое программирование.
21 ответ
Хорошо, сначала я опишу самое простое решение - O(N^2), где N - размер коллекции. Также существует решение O(N log N), которое я также опишу. Ищите здесь это в разделе Эффективные алгоритмы.
Я буду предполагать, что индексы массива от 0 до N - 1. Итак, давайте определимся DP[i] быть длиной LIS (самая длинная возрастающая подпоследовательность), которая заканчивается в элементе с индексом i, Вычислить DP[i] мы смотрим на все показатели j < i и проверьте оба, если DP[j] + 1 > DP[i] а также array[j] < array[i] (мы хотим, чтобы это увеличивалось). Если это правда, мы можем обновить текущий оптимум для DP[i], Чтобы найти глобальный оптимум для массива, вы можете взять максимальное значение из DP[0...N - 1],
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
Я использую массив prev чтобы потом можно было найти фактическую последовательность, а не только ее длину. Просто вернись рекурсивно из bestEnd в цикле, используя prev[bestEnd], -1 Значение является признаком остановки.
Хорошо, теперь к более эффективному O(N log N) решение:
Позволять S[pos] быть определено как наименьшее целое число, которое заканчивается возрастающей последовательностью длины pos, Теперь перебираем каждое целое число X из набора ввода и выполните следующие действия:
Если
X> последний элемент вS, а затем добавитьXдо концаS, Это существенно означает, что мы нашли новый по величинеLIS,В противном случае найдите самый маленький элемент в
S, который>=чемXи измените его наX, Так какSсортируется в любое время, элемент можно найти с помощью бинарного поиска вlog(N),
Общее время выполнения - N целые числа и бинарный поиск для каждого из них - N * log(N) = O(N log N)
Теперь давайте сделаем реальный пример:
Коллекция целых чисел:2 6 3 4 1 2 9 5 8
шаги:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
Таким образом, длина LIS 5 (размер S).
Чтобы восстановить фактическое LIS мы снова будем использовать родительский массив. Позволять parent[i] быть предшественником элемента с индексом i в LIS заканчивается на элементе индексом i,
Чтобы сделать вещи проще, мы можем сохранить в массиве Sне фактические целые числа, а их индексы (позиции) в наборе. Мы не держим {1, 2, 4, 5, 8}, но продолжай {4, 5, 3, 7, 8},
То есть вход [4] = 1, вход [5] = 2, вход [3] = 4, вход [7] = 5, вход [8] = 8.
Если мы правильно обновим родительский массив, фактическая LIS будет:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
Теперь важная вещь - как мы обновляем родительский массив? Есть два варианта:
Если
X> последний элемент вS, затемparent[indexX] = indexLastElement, Это означает, что родительский элемент нового элемента является последним элементом. Мы просто готовимсяXдо концаS,В противном случае найдите индекс наименьшего элемента в
S, который>=чемXи измените его наX, Вотparent[indexX] = S[index - 1],
Объяснения Петара Минчева помогли мне все прояснить, но мне было трудно разобрать, что именно, поэтому я сделал реализацию Python с чрезмерно описательными именами переменных и множеством комментариев. Я сделал наивное рекурсивное решение, решение O(n^2) и решение O(n log n).
Я надеюсь, что это помогает прояснить алгоритмы!
Рекурсивное решение
def recursive_solution(remaining_sequence, bigger_than=None):
"""Finds the longest increasing subsequence of remaining_sequence that is
bigger than bigger_than and returns it. This solution is O(2^n)."""
# Base case: nothing is remaining.
if len(remaining_sequence) == 0:
return remaining_sequence
# Recursive case 1: exclude the current element and process the remaining.
best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)
# Recursive case 2: include the current element if it's big enough.
first = remaining_sequence[0]
if (first > bigger_than) or (bigger_than is None):
sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)
# Choose whichever of case 1 and case 2 were longer.
if len(sequence_with) >= len(best_sequence):
best_sequence = sequence_with
return best_sequence
O(n^2) решение для динамического программирования
def dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming. This solution is O(n^2)."""
longest_subsequence_ending_with = []
backreference_for_subsequence_ending_with = []
current_best_end = 0
for curr_elem in range(len(sequence)):
# It's always possible to have a subsequence of length 1.
longest_subsequence_ending_with.append(1)
# If a subsequence is length 1, it doesn't have a backreference.
backreference_for_subsequence_ending_with.append(None)
for prev_elem in range(curr_elem):
subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)
# If the prev_elem is smaller than the current elem (so it's increasing)
# And if the longest subsequence from prev_elem would yield a better
# subsequence for curr_elem.
if ((sequence[prev_elem] < sequence[curr_elem]) and
(subsequence_length_through_prev >
longest_subsequence_ending_with[curr_elem])):
# Set the candidate best subsequence at curr_elem to go through prev.
longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
backreference_for_subsequence_ending_with[curr_elem] = prev_elem
# If the new end is the best, update the best.
if (longest_subsequence_ending_with[curr_elem] >
longest_subsequence_ending_with[current_best_end]):
current_best_end = curr_elem
# Output the overall best by following the backreferences.
best_subsequence = []
current_backreference = current_best_end
while current_backreference is not None:
best_subsequence.append(sequence[current_backreference])
current_backreference = (backreference_for_subsequence_ending_with[current_backreference])
best_subsequence.reverse()
return best_subsequence
Решение для динамического программирования O(n log n)
def find_smallest_elem_as_big_as(sequence, subsequence, elem):
"""Returns the index of the smallest element in subsequence as big as
sequence[elem]. sequence[elem] must not be larger than every element in
subsequence. The elements in subsequence are indices in sequence. Uses
binary search."""
low = 0
high = len(subsequence) - 1
while high > low:
mid = (high + low) / 2
# If the current element is not as big as elem, throw out the low half of
# sequence.
if sequence[subsequence[mid]] < sequence[elem]:
low = mid + 1
# If the current element is as big as elem, throw out everything bigger, but
# keep the current element.
else:
high = mid
return high
def optimized_dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming and binary search (per
http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution
is O(n log n)."""
# Both of these lists hold the indices of elements in sequence and not the
# elements themselves.
# This list will always be sorted.
smallest_end_to_subsequence_of_length = []
# This array goes along with sequence (not
# smallest_end_to_subsequence_of_length). Following the corresponding element
# in this array repeatedly will generate the desired subsequence.
parent = [None for _ in sequence]
for elem in range(len(sequence)):
# We're iterating through sequence in order, so if elem is bigger than the
# end of longest current subsequence, we have a new longest increasing
# subsequence.
if (len(smallest_end_to_subsequence_of_length) == 0 or
sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
# If we are adding the first element, it has no parent. Otherwise, we
# need to update the parent to be the previous biggest element.
if len(smallest_end_to_subsequence_of_length) > 0:
parent[elem] = smallest_end_to_subsequence_of_length[-1]
smallest_end_to_subsequence_of_length.append(elem)
else:
# If we can't make a longer subsequence, we might be able to make a
# subsequence of equal size to one of our earlier subsequences with a
# smaller ending number (which makes it easier to find a later number that
# is increasing).
# Thus, we look for the smallest element in
# smallest_end_to_subsequence_of_length that is at least as big as elem
# and replace it with elem.
# This preserves correctness because if there is a subsequence of length n
# that ends with a number smaller than elem, we could add elem on to the
# end of that subsequence to get a subsequence of length n+1.
location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
smallest_end_to_subsequence_of_length[location_to_replace] = elem
# If we're replacing the first element, we don't need to update its parent
# because a subsequence of length 1 has no parent. Otherwise, its parent
# is the subsequence one shorter, which we just added onto.
if location_to_replace != 0:
parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])
# Generate the longest increasing subsequence by backtracking through parent.
curr_parent = smallest_end_to_subsequence_of_length[-1]
longest_increasing_subsequence = []
while curr_parent is not None:
longest_increasing_subsequence.append(sequence[curr_parent])
curr_parent = parent[curr_parent]
longest_increasing_subsequence.reverse()
return longest_increasing_subsequence
Говоря о решении DP, я обнаружил удивление, что никто не упомянул тот факт, что LIS может быть сокращен до LCS. Все, что вам нужно сделать, это отсортировать копию оригинальной последовательности, удалить все дубликаты и сделать из них LCS. В псевдокоде это:
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
И полная реализация написана на Go. Вам не нужно поддерживать всю матрицу n^2 DP, если вам не нужно восстанавливать решение.
func lcs(arr1 []int) int {
arr2 := make([]int, len(arr1))
for i, v := range arr1 {
arr2[i] = v
}
sort.Ints(arr1)
arr3 := []int{}
prev := arr1[0] - 1
for _, v := range arr1 {
if v != prev {
prev = v
arr3 = append(arr3, v)
}
}
n1, n2 := len(arr1), len(arr3)
M := make([][]int, n2 + 1)
e := make([]int, (n1 + 1) * (n2 + 1))
for i := range M {
M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)]
}
for i := 1; i <= n2; i++ {
for j := 1; j <= n1; j++ {
if arr2[j - 1] == arr3[i - 1] {
M[i][j] = M[i - 1][j - 1] + 1
} else if M[i - 1][j] > M[i][j - 1] {
M[i][j] = M[i - 1][j]
} else {
M[i][j] = M[i][j - 1]
}
}
}
return M[n2][n1]
}
Следующая реализация C++ также включает в себя некоторый код, который создает фактическую самую длинную увеличивающуюся подпоследовательность, используя массив с именем prev,
std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
int best_end = 0;
int sz = s.size();
if (!sz)
return std::vector<int>();
std::vector<int> prev(sz,-1);
std::vector<int> memo(sz, 0);
int max_length = std::numeric_limits<int>::min();
memo[0] = 1;
for ( auto i = 1; i < sz; ++i)
{
for ( auto j = 0; j < i; ++j)
{
if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
{
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if ( memo[i] > max_length )
{
best_end = i;
max_length = memo[i];
}
}
// Code that builds the longest increasing subsequence using "prev"
std::vector<int> results;
results.reserve(sz);
std::stack<int> stk;
int current = best_end;
while (current != -1)
{
stk.push(s[current]);
current = prev[current];
}
while (!stk.empty())
{
results.push_back(stk.top());
stk.pop();
}
return results;
}
Реализация без стека просто обратный вектор
#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
auto sz = v.size();
if(!sz)
return v;
std::vector<int> memo(sz, 0);
std::vector<int> prev(sz, -1);
memo[0] = 1;
int best_end = 0;
int max_length = std::numeric_limits<int>::min();
for (auto i = 1; i < sz; ++i) {
for ( auto j = 0; j < i ; ++j) {
if (s[j] < s[i] && memo[i] < memo[j] + 1) {
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if(memo[i] > max_length) {
best_end = i;
max_length = memo[i];
}
}
// create results
std::vector<int> results;
results.reserve(v.size());
auto current = best_end;
while (current != -1) {
results.push_back(s[current]);
current = prev[current];
}
std::reverse(results.begin(), results.end());
return results;
}
Вот три шага оценки проблемы с точки зрения динамического программирования:
- Определение повторения: maxLength(i) == 1 + maxLength(j), где 0
array[j] - Граница параметра повторения: может быть от 0 до i - 1 подпоследовательность, переданная как параметр
- Порядок оценки: поскольку это возрастающая подпоследовательность, она должна быть оценена от 0 до n
Если мы возьмем в качестве примера последовательность {0, 8, 2, 3, 7, 9}, по индексу:
- [0] мы получим подпоследовательность {0} в качестве базового варианта
- [1] у нас есть 1 новая подпоследовательность {0, 8}
- [2] пытается оценить две новые последовательности {0, 8, 2} и {0, 2}, добавив элемент с индексом 2 к существующим подпоследовательностям - допустима только одна, поэтому добавляется только третья возможная последовательность {0, 2} к списку параметров...
Вот рабочий код C++11:
#include <iostream>
#include <vector>
int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
if(index == 0) {
sub.push_back(std::vector<int>{sequence[0]});
return 1;
}
size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
std::vector<std::vector<int>> tmpSubSeq;
for(std::vector<int> &subSeq : sub) {
if(subSeq[subSeq.size() - 1] < sequence[index]) {
std::vector<int> newSeq(subSeq);
newSeq.push_back(sequence[index]);
longestSubSeq = std::max(longestSubSeq, newSeq.size());
tmpSubSeq.push_back(newSeq);
}
}
std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
std::back_insert_iterator<std::vector<std::vector<int>>>(sub));
return longestSubSeq;
}
int getLongestIncSub(const std::vector<int> &sequence) {
std::vector<std::vector<int>> sub;
return getLongestIncSub(sequence, sequence.size() - 1, sub);
}
int main()
{
std::vector<int> seq{0, 8, 2, 3, 7, 9};
std::cout << getLongestIncSub(seq);
return 0;
}
Вот реализация Java O(Nlogn)
import java.util.Scanner;
public class LongestIncreasingSeq {
private static int binarySearch(int table[],int a,int len){
int end = len-1;
int beg = 0;
int mid = 0;
int result = -1;
while(beg <= end){
mid = (end + beg) / 2;
if(table[mid] < a){
beg=mid+1;
result = mid;
}else if(table[mid] == a){
return len-1;
}else{
end = mid-1;
}
}
return result;
}
public static void main(String[] args) {
// int[] t = {1, 2, 5,9,16};
// System.out.println(binarySearch(t , 9, 5));
Scanner in = new Scanner(System.in);
int size = in.nextInt();//4;
int A[] = new int[size];
int table[] = new int[A.length];
int k = 0;
while(k<size){
A[k++] = in.nextInt();
if(k<size-1)
in.nextLine();
}
table[0] = A[0];
int len = 1;
for (int i = 1; i < A.length; i++) {
if(table[0] > A[i]){
table[0] = A[i];
}else if(table[len-1]<A[i]){
table[len++]=A[i];
}else{
table[binarySearch(table, A[i],len)+1] = A[i];
}
}
System.out.println(len);
}
}
Вот еще одна реализация O(n^2) JAVA. Нет рекурсии / запоминания для генерации фактической подпоследовательности. Просто строковый массив, который хранит фактическую LIS на каждом этапе и массив для хранения длины LIS для каждого элемента. Довольно чертовски легко. Посмотри:
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
* Created by Shreyans on 4/16/2015
*/
class LNG_INC_SUB//Longest Increasing Subsequence
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter Numbers Separated by Spaces to find their LIS\n");
String[] s1=br.readLine().split(" ");
int n=s1.length;
int[] a=new int[n];//Array actual of Numbers
String []ls=new String[n];// Array of Strings to maintain LIS for every element
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s1[i]);
}
int[]dp=new int[n];//Storing length of max subseq.
int max=dp[0]=1;//Defaults
String seq=ls[0]=s1[0];//Defaults
for(int i=1;i<n;i++)
{
dp[i]=1;
String x="";
for(int j=i-1;j>=0;j--)
{
//First check if number at index j is less than num at i.
// Second the length of that DP should be greater than dp[i]
// -1 since dp of previous could also be one. So we compare the dp[i] as empty initially
if(a[j]<a[i]&&dp[j]>dp[i]-1)
{
dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j]
x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on
}
}
x+=(" "+a[i]);
ls[i]=x;
if(dp[i]>max)
{
max=dp[i];
seq=ls[i];
}
}
System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq);
}
}
Код в действии: http://ideone.com/sBiOQx
Вот реализация Scala алгоритма O(n^2):
object Solve {
def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
xs.foldLeft(List[(Int, List[T])]()) {
(sofar, x) =>
if (sofar.isEmpty) List((1, List(x)))
else {
val resIfEndsAtCurr = (sofar, xs).zipped map {
(tp, y) =>
val len = tp._1
val seq = tp._2
if (ord.lteq(y, x)) {
(len + 1, x :: seq) // reversely recorded to avoid O(n)
} else {
(1, List(x))
}
}
sofar :+ resIfEndsAtCurr.maxBy(_._1)
}
}.maxBy(_._1)._2.reverse
}
def main(args: Array[String]) = {
println(longestIncrSubseq(List(
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)))
}
}
Простейшее решение LIS в C++ с O(nlog(n)) сложностью по времени
#include <iostream>
#include "vector"
using namespace std;
// binary search (If value not found then it will return the index where the value should be inserted)
int ceilBinarySearch(vector<int> &a,int beg,int end,int value)
{
if(beg<=end)
{
int mid = (beg+end)/2;
if(a[mid] == value)
return mid;
else if(value < a[mid])
return ceilBinarySearch(a,beg,mid-1,value);
else
return ceilBinarySearch(a,mid+1,end,value);
return 0;
}
return beg;
}
int lis(vector<int> arr)
{
vector<int> dp(arr.size(),0);
int len = 0;
for(int i = 0;i<arr.size();i++)
{
int j = ceilBinarySearch(dp,0,len-1,arr[i]);
dp[j] = arr[i];
if(j == len)
len++;
}
return len;
}
int main()
{
vector<int> arr {2, 5,-1,0,6,1,2};
cout<<lis(arr);
return 0;
}
ВЫХОД:
4
Подход O(NLog(N)) для поиска
самой длинной возрастающей подпоследовательности. Давайте будем поддерживать массив, где i-й элемент является наименьшим возможным числом, которым может заканчиваться подпоследовательность размера ai.
Я специально избегаю дополнительных подробностей, поскольку ответ, получивший наибольшее количество голосов, уже объясняет это, но этот метод в конечном итоге приводит к аккуратной реализации с использованием заданной структуры данных (по крайней мере, в C++).
Вот реализация на С ++ (при условии, что требуется строго увеличивать размер самой длинной подпоследовательности)
#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;
int main()
{
ll n;
cin >> n;
ll arr[n];
set<ll> S;
for(ll i=0; i<n; i++)
{
cin >> arr[i];
auto it = S.lower_bound(arr[i]);
if(it != S.end())
S.erase(it);
S.insert(arr[i]);
}
cout << S.size() << endl; // Size of the set is the required answer
return 0;
}
Это может быть решено в O(n^2) с помощью динамического программирования. Код Python для того же будет выглядеть так:
def LIS(numlist):
LS = [1]
for i in range(1, len(numlist)):
LS.append(1)
for j in range(0, i):
if numlist[i] > numlist[j] and LS[i]<=LS[j]:
LS[i] = 1 + LS[j]
print LS
return max(LS)
numlist = map(int, raw_input().split(' '))
print LIS(numlist)
Для ввода:5 19 5 81 50 28 29 1 83 23
вывод будет:[1, 2, 1, 3, 3, 3, 4, 1, 5, 3]
5
List_index списка вывода является list_index списка ввода. Значение данного list_index в выходном списке обозначает самую длинную увеличивающуюся длину подпоследовательности для этого list_index.
Используя динамическое программирование [Подход 1], эту проблему можно решить в
def lis_dp(array):
alias = [1] * len(array)
for i in range(1, len(array)):
for j in range(0, i):
if array[i] > array[j]:
alias[i] = max(alias[i], alias[j] + 1)
output = max(alias)
return output
arr = [4, 10, 6, 5, 8, 11, 2, 20]
output = lis_dp(array=arr)
print(output)
Анализ временной сложности подхода 1: это
Второй подход: использование двоичного поиска.
Эту проблему можно решить в
Теория:
Хвостовой массив построен, и длина хвостового массива является ответом.
Tail[i] хранит минимально возможное значение хвоста для LIS длиной (i + 1), где i находится в диапазоне от (0, n), где n — длина данного массива.
Два условия при создании хвостового массива
Условие 1: Если следующий элемент, который нужно вставить в хвостовой массив, больше предыдущего, то элемент добавляется.
Условие 2: Если следующий элемент, который будет вставлен в хвостовой массив, меньше предыдущего элемента, он заменит его потолок слева.
Угловой шкаф
Случай 1: если у нас есть массив, отсортированный в порядке убывания, результат равен 1.
Случай 2: Если у нас есть массив, отсортированный в порядке возрастания, результат будет длиной (массив).
Примечание. Краевые случаи остаются одинаковыми как для динамического программирования, так и для подхода двоичного поиска.
Давайте посмотрим код для подхода 2
def ceil_idx(tail, x):
l = 0
r = len(tail) - 1
while r > l:
m = l + (r - l)//2
if tail[m] >= x:
r = m
else:
l = m + 1
return r
def lis_bs(array):
n = len(array)
tail = [array[0]]
for i in range(1, n):
# condition 1: If the next element to be inserted in the tail array is greater than previous one, then element is appended.
if array[i] > tail[-1]:
tail.append(array[i])
else:
# condition 2: If the next element to be inserted in the tail array is smaller than previous element then it will replace it ceiling to its left.
c = ceil_idx(tail, array[i])
tail[c] = array[i]
return len(tail)
arr = [4, 10, 6, 5, 8, 11, 2, 20]
output_lis = lis_bs(array=arr)
print(output_lis)
Анализ временной сложности второго подхода
Поскольку существует цикл for, который выполняется до достижения длины массива, следовательно, он займет тета (n) раз, и внутри этого цикла выполняется еще одна функция, которая представляет собой двоичный поиск (функция потолка), которая занимает log (n) раз и, следовательно, общее затраченное время равно nlog . (н) .
Рекурсивный подход DP O(NLog(N)) к поиску самой длинной возрастающей подпоследовательности (LIS)
Объяснение
Этот алгоритм включает создание дерева с форматом узла как
(a,b).
представляет следующий элемент, который мы рассматриваем как добавление к действительной подпоследовательности.
представляет начальный индекс оставшегося подмассива, из которого будет принято следующее решение, если он будет добавлен в конец подмассива, который у нас есть до сих пор.
Алгоритм
Мы начинаем с недопустимого корня (INT_MIN,0), указывая на нулевой индекс массива, поскольку подпоследовательность в этой точке пуста, т.е.
b = 0.Base Case: вернуть, еслиb >= array.length.Прокрутите все элементы в массиве из
bиндекс до конца массива, т.е.i = b ... array.length-1. i) Если элемент,array[i]являетсяgreater thanтекущий, он квалифицируется как один из элементов, добавляемых к подпоследовательности, которая у нас есть до сих пор. ii) Рекурсия в узел(array[i],b+1), где - элемент, с которым мы столкнулись в2(i)который может быть добавлен к уже имеющейся подпоследовательности. А такжеb+1это следующий индекс массива, который необходимо рассмотреть. iii) Вернитеmaxдлина, полученная путем прохожденияi = b ... array.length. В случае, когдаaбольше любого другого элемента изi = b to array.length, возвращаться1.Вычислите уровень дерева, построенного как
level. Ну наконец то,level - 1желаемыйLIS. Это количествоedgesна самом длинном пути дерева.
NB : Запоминание в алгоритме не учитывается, так как оно ясно из дерева.
Отмечены случайные примеры узлов
x извлекаются из мемоизированных значений БД. 
Реализация Java
public int lengthOfLIS(int[] nums) {
return LIS(nums,Integer.MIN_VALUE, 0,new HashMap<>()) -1;
}
public int LIS(int[] arr, int value, int nextIndex, Map<String,Integer> memo){
if(memo.containsKey(value+","+nextIndex))return memo.get(value+","+nextIndex);
if(nextIndex >= arr.length)return 1;
int max = Integer.MIN_VALUE;
for(int i=nextIndex; i<arr.length; i++){
if(arr[i] > value){
max = Math.max(max,LIS(arr,arr[i],i+1,memo));
}
}
if(max == Integer.MIN_VALUE)return 1;
max++;
memo.put(value+","+nextIndex,max);
return max;
}
Проверить код в Java для самой длинной увеличивающейся подпоследовательности с элементами массива
/**
** Java Program to implement Longest Increasing Subsequence Algorithm
**/
import java.util.Scanner;
/** Class LongestIncreasingSubsequence **/
class LongestIncreasingSubsequence
{
/** function lis **/
public int[] lis(int[] X)
{
int n = X.length - 1;
int[] M = new int[n + 1];
int[] P = new int[n + 1];
int L = 0;
for (int i = 1; i < n + 1; i++)
{
int j = 0;
/** Linear search applied here. Binary Search can be applied too.
binary search for the largest positive j <= L such that
X[M[j]] < X[i] (or set j = 0 if no such value exists) **/
for (int pos = L ; pos >= 1; pos--)
{
if (X[M[pos]] < X[i])
{
j = pos;
break;
}
}
P[i] = M[j];
if (j == L || X[i] < X[M[j + 1]])
{
M[j + 1] = i;
L = Math.max(L,j + 1);
}
}
/** backtrack **/
int[] result = new int[L];
int pos = M[L];
for (int i = L - 1; i >= 0; i--)
{
result[i] = X[pos];
pos = P[pos];
}
return result;
}
/** Main Function **/
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Longest Increasing Subsequence Algorithm Test\n");
System.out.println("Enter number of elements");
int n = scan.nextInt();
int[] arr = new int[n + 1];
System.out.println("\nEnter "+ n +" elements");
for (int i = 1; i <= n; i++)
arr[i] = scan.nextInt();
LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence();
int[] result = obj.lis(arr);
/** print result **/
System.out.print("\nLongest Increasing Subsequence : ");
for (int i = 0; i < result.length; i++)
System.out.print(result[i] +" ");
System.out.println();
}
}
Вот мое решение Leetcode с использованием бинарного поиска:->
class Solution:
def binary_search(self,s,x):
low=0
high=len(s)-1
flag=1
while low<=high:
mid=(high+low)//2
if s[mid]==x:
flag=0
break
elif s[mid]<x:
low=mid+1
else:
high=mid-1
if flag:
s[low]=x
return s
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
s=[]
s.append(nums[0])
for i in range(1,len(nums)):
if s[-1]<nums[i]:
s.append(nums[i])
else:
s=self.binary_search(s,nums[i])
return len(s)
O(n^2) Java-реализация:
void LIS(int arr[]){
int maxCount[]=new int[arr.length];
int link[]=new int[arr.length];
int maxI=0;
link[0]=0;
maxCount[0]=0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if(arr[j]<arr[i] && ((maxCount[j]+1)>maxCount[i])){
maxCount[i]=maxCount[j]+1;
link[i]=j;
if(maxCount[i]>maxCount[maxI]){
maxI=i;
}
}
}
}
for (int i = 0; i < link.length; i++) {
System.out.println(arr[i]+" "+link[i]);
}
print(arr,maxI,link);
}
void print(int arr[],int index,int link[]){
if(link[index]==index){
System.out.println(arr[index]+" ");
return;
}else{
print(arr, link[index], link);
System.out.println(arr[index]+" ");
}
}
Это может быть решено в O(n^2) с помощью динамического программирования.
Обработайте элементы ввода по порядку и ведите список кортежей для каждого элемента. Каждый кортеж (A,B) для элемента i будет обозначать, A = длина самой длинной увеличивающейся подпоследовательности, заканчивающейся в i, и B = индекс предшественника списка [i] в самой длинной увеличивающейся подпоследовательности, заканчивающейся в списке [i].
Начните с элемента 1, список кортежей для элемента 1 будет [(1,0)] для элемента i, просканируйте список 0..i и найдите список элементов [k] такой, что list[k] В конце найдите все элементы с максимальным значением A (длина LIS, заканчивающаяся на элементе) и вернитесь назад, используя кортежи, чтобы получить список. Я поделился кодом для того же на http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799
Это реализация Java в O(n^2). Я просто не использовал Бинарный поиск, чтобы найти наименьший элемент в S, который>> чем X. Я просто использовал цикл for. Использование бинарного поиска усложнит задачу за O(n logn)
public static void olis(int[] seq){
int[] memo = new int[seq.length];
memo[0] = seq[0];
int pos = 0;
for (int i=1; i<seq.length; i++){
int x = seq[i];
if (memo[pos] < x){
pos++;
memo[pos] = x;
} else {
for(int j=0; j<=pos; j++){
if (memo[j] >= x){
memo[j] = x;
break;
}
}
}
//just to print every step
System.out.println(Arrays.toString(memo));
}
//the final array with the LIS
System.out.println(Arrays.toString(memo));
System.out.println("The length of lis is " + (pos + 1));
}
Самая длинная возрастающая подпоследовательность (Java)
import java.util.*;
class ChainHighestValue implements Comparable<ChainHighestValue>{
int highestValue;
int chainLength;
ChainHighestValue(int highestValue,int chainLength) {
this.highestValue = highestValue;
this.chainLength = chainLength;
}
@Override
public int compareTo(ChainHighestValue o) {
return this.chainLength-o.chainLength;
}
}
public class LongestIncreasingSubsequenceLinkedList {
private static LinkedList<Integer> LongestSubsequent(int arr[], int size){
ArrayList<LinkedList<Integer>> seqList=new ArrayList<>();
ArrayList<ChainHighestValue> valuePairs=new ArrayList<>();
for(int i=0;i<size;i++){
int currValue=arr[i];
if(valuePairs.size()==0){
LinkedList<Integer> aList=new LinkedList<>();
aList.add(arr[i]);
seqList.add(aList);
valuePairs.add(new ChainHighestValue(arr[i],1));
}else{
try{
ChainHighestValue heighestIndex=valuePairs.stream().filter(e->e.highestValue<currValue).max(ChainHighestValue::compareTo).get();
int index=valuePairs.indexOf(heighestIndex);
seqList.get(index).add(arr[i]);
heighestIndex.highestValue=arr[i];
heighestIndex.chainLength+=1;
}catch (Exception e){
LinkedList<Integer> aList=new LinkedList<>();
aList.add(arr[i]);
seqList.add(aList);
valuePairs.add(new ChainHighestValue(arr[i],1));
}
}
}
ChainHighestValue heighestIndex=valuePairs.stream().max(ChainHighestValue::compareTo).get();
int index=valuePairs.indexOf(heighestIndex);
return seqList.get(index);
}
public static void main(String[] args){
int arry[]={5,1,3,6,11,30,32,5,3,73,79};
//int arryB[]={3,1,5,2,6,4,9};
LinkedList<Integer> LIS=LongestSubsequent(arry, arry.length);
System.out.println("Longest Incrementing Subsequence:");
for(Integer a: LIS){
System.out.print(a+" ");
}
}
}
Я реализовал LIS на java, используя динамическое программирование и мемоизацию. Наряду с кодом я сделал расчет сложности, то есть почему это O(n Log(base2) n). Насколько я понимаю, теоретические или логические объяснения хороши, но практическая демонстрация всегда лучше для понимания.
package com.company.dynamicProgramming;
import java.util.HashMap;
import java.util.Map;
public class LongestIncreasingSequence {
static int complexity = 0;
public static void main(String ...args){
int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = arr.length;
Map<Integer, Integer> memo = new HashMap<>();
lis(arr, n, memo);
//Display Code Begins
int x = 0;
System.out.format("Longest Increasing Sub-Sequence with size %S is -> ",memo.get(n));
for(Map.Entry e : memo.entrySet()){
if((Integer)e.getValue() > x){
System.out.print(arr[(Integer)e.getKey()-1] + " ");
x++;
}
}
System.out.format("%nAnd Time Complexity for Array size %S is just %S ", arr.length, complexity );
System.out.format( "%nWhich is equivalent to O(n Log n) i.e. %SLog(base2)%S is %S",arr.length,arr.length, arr.length * Math.ceil(Math.log(arr.length)/Math.log(2)));
//Display Code Ends
}
static int lis(int[] arr, int n, Map<Integer, Integer> memo){
if(n==1){
memo.put(1, 1);
return 1;
}
int lisAti;
int lisAtn = 1;
for(int i = 1; i < n; i++){
complexity++;
if(memo.get(i)!=null){
lisAti = memo.get(i);
}else {
lisAti = lis(arr, i, memo);
}
if(arr[i-1] < arr[n-1] && lisAti +1 > lisAtn){
lisAtn = lisAti +1;
}
}
memo.put(n, lisAtn);
return lisAtn;
}
}
Пока я запускал приведенный выше код -
Longest Increasing Sub-Sequence with size 6 is -> 10 22 33 50 60 80
And Time Complexity for Array size 9 is just 36
Which is equivalent to O(n Log n) i.e. 9Log(base2)9 is 36.0
Process finished with exit code 0
def longestincrsub(arr1):
n=len(arr1)
l=[1]*n
for i in range(0,n):
for j in range(0,i) :
if arr1[j]<arr1[i] and l[i]<l[j] + 1:
l[i] =l[j] + 1
l.sort()
return l[-1]
arr1=[10,22,9,33,21,50,41,60]
a=longestincrsub(arr1)
print(a)
хотя есть способ, которым вы можете решить это за O(nlogn) время (это решает за O(n^2) время), но все же этот способ дает подход динамического программирования, который также хорош.