Longest Increasing Subsequence (LIS) - это подпоследовательность в массиве чисел с возрастающим порядком. Числа в подпоследовательности должны быть уникальными и располагаться в порядке возрастания. Важно отметить, что элементы последовательности не обязательно должны находиться в последовательных местах в массиве.
Можете ли вы написать эффективную программу, которая находит длину Longest Increasing Subsequence, также называемую LIS?
Изначально этот урок был опубликован на https://algodaily.com, где я веду курс технических собеседований и пишу мысли для амбициозных разработчиков.
Примеры
Вот несколько примеров и их решения:
Input: {1,5,2,7,3}
LIS = 3. The longest increasing subsequence could be any of {1,5,7},{1,2,3},{1,2,7}
Input: {13,1,3,4,8,4}
LIS = 4. The longest increasing subsequence {1,3,4,8}
Input: {13,1,3,4,8,19,17,8,0,20,14}
LIS = 6. The longest increasing subsequence {1,3,4,8,17,20},{1,3,4,8,19,20}
Как решить ЛИС
В этом руководстве я буду называть самую длинную возрастающую подпоследовательность LIS. Давайте сначала рассмотрим простой рекурсивный метод, который может найти LIS для массива. Для объяснения мы будем использовать следующие обозначения:
LIS(arr, n): Length of longest increasing sub-sequence that has arr[n] as "its last item".
Давайте посмотрим на приведенные ниже примеры. Здесь все индексы начинаются с нуля. Сейчас мы просто исследуем некоторые закономерности:
// in the below example, we're looking for arr[0], which is 1
LIS({1,3,4,0}, 0) = 1 // solution is the subsequence {1}
// continuing the pattern
LIS({1,3,4,0}, 1) = 2 // the subsequence {1,3}
LIS({1,3,4,0}, 2) = 3 // the subsequence {1,3,4}
LIS({1,3,4,0}, 3) = 1 // the subsequence {0} as it has to include arr[3]
Появляются некоторые наблюдения: поскольку подпоследовательность должна заканчиваться на arr[n], она может включать только элементы, удовлетворяющие двум условиям:
- Элементы должны иметь индекс меньше
n(меньше) - Элементы должны быть меньше
arr[n].
Таким образом, мы можем извлечь следующее правило:
LIS(arr, n) = 1 + max( LIS(arr, j) ) max computed over all j, 0<=j<n and arr[j]<arr[n]`
Мы можем перевести это на английский язык: если мы сможем найти LIS(arr, n) (LIS с arr [n] в качестве последнего элемента) для всех индексов массива, то longest increasing subsequence для всего массива LISMax(arr) будет максимумом из LIS(arr, n), вычислено для всех допустимых индексов n:
LISMax(arr) = max( LIS(n) ) max computed for all valid indices n of the array
Псевдокод
Теперь, когда у нас есть простое правило для решения проблемы, давайте напишем для него псевдокод.
Routine: LISMax(arr)
Input: array of size S
Output: Length of longest increasing subsequence
LISMax(arr)
1. max = 0
2. Loop from n = 0..(S-1)
a. Compute temp = LIS(arr,n)
b. if temp > max then max = temp
return max
В качестве альтернативы ниже приведен псевдокод для вычисления LIS с двумя параметрами:
Routine: LIS(arr,n)
Input: array of size S and index n
Output: Length of longest increasing subsequence that has arr[n] as its last item
LIS(arr,n)
Base case:
1. if (n==0) return 1
Recursive case:
1. max = 1
2. Loop from j=0..(n-1)
a. if (arr[j]<arr[n])
i. compute temp = LIS(arr,j)
ii. if (temp>max) then max=temp
return max
Чтобы увидеть, как работает этот псевдокод, я привел пример вычисления LIS для {2,3,8,5,6} для индекса 4. Таким образом, подпоследовательность должна включать число 6 в качестве последнего элемента.
На рисунке показано, что LIS(arr, 0) нужно вычислять снова и снова. То же самое и с LIS(arr, 1). Для больших значений n будет много значений, для которых функция должна быть повторена. Это привело бы к временной сложности O (2 ^ n), которая является экспоненциальной. Как компьютерные ученые, мы знаем, что это не практическое решение.
Динамическое программирование на помощь
Основной принцип dynamic programming заключается в том, что если ваше решение имеет рекурсивную структуру, вы можете:
- Разбейте проблему на более мелкие подзадачи
- Сохраните решения подзадач и используйте их позже при необходимости
Например, LIS(arr, 0) и LIS(arr, 1) пересчитываются и требуются снова и снова. В качестве альтернативы, после вычисления мы можем сохранить их в массиве и использовать этот результат всякий раз, когда это необходимо.
Следовательно, теперь мы должны учитывать дополнительный массив. Назовем этот массив LISArr, в котором хранится значение LIS(arr, n) с индексом n.
- Инициализируйте каждый элемент
LISArrнулевым значением. - Если требуется
LIS(arr, n), проверьте значениеLISArr[n].
2а. Если LISArr [n] равно нулю, вычислить LIS (arr, n) и сохранить в LISArr [n]
2b. Если LISArr [n] больше нуля, просто используйте его значение из массива.
Теперь пришло время изменить предыдущий псевдокод, чтобы включить динамическое программирование. Необходимо изменить только процедуру LIS(arr, n) с одним дополнительным параметром для включения массива LISArr.
Мы видим, что временная сложность этого псевдокода по-прежнему квадратична, то есть O(n^2). Функция LISDP выполняется для каждого элемента массива, и для каждого элемента LIS выполняется не более n раз. Это делает общую сложность O(n^2).
Routine: LISDP(arr,n,LISArr)
Input: array of size S and index n, length array same size as arr and initialized to zero
Output: Length of longest increasing subsequence that has arr[n] as its last item
LISDP(arr,n,LISArr)
Base case:
1. if (n==0) return 1
2. if LISArr[n] != 0 return LISArr[n] //do not go in the recursive case
Recursive case:
1. max = 1
2. Loop from j=0..(n-1)
a. if (arr[j]<arr[n])
i. if LISArr[j]==0 then LISArr[j] = LISDP(arr,j,LISArr) //compute LIS(arr,j) if necessary
ii. temp = LISArr[j]
iii. if (temp>max) then max=temp
return max
Код C ++ для LIS с использованием динамического программирования
Наконец, вот код для реализации LIS с использованием динамического программирования. Как всегда, мы советуем вам продумать все на бумаге, прежде чем что-либо реализовывать.
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
class LISsolveDP
{
//recursive function to return LIS(arr,n) as described
int LISDP(vector<int> arr,int ind,vector<int> & LISArr)
{
int i=0;
if (LISArr[ind] !=0)
return LISArr[ind];
if (ind == 0)
{
LISArr[ind]=1;
return 1;
}
int temp=0,max=1;
for (i=0;i<ind;++i)
{
temp = LISArr[i];
if (temp==0)
temp = LISDP(arr,i,LISArr);
if (arr[i]<arr[ind])
temp++;
if (temp>max && arr[i]<arr[ind])
{
max = temp;
//uncomment below to understand
//cout << "...ind = " << ind<< " i=" << i << " max= " << max << "\n";
}
}
LISArr[ind] = max;
return max;
}
public:
int LIS(vector<int> arr)
{
int result = 0,temp=0;
//initialize LISArr
vector<int> LISArr(arr.size(),0);
for (int i=0;i<arr.size();++i)
{
temp = LISDP(arr,i,LISArr);
if (temp>result)
result = temp;
}
return result;
}
};
class LISsolveFast
{
//temporary array that stores the index of all end elements
//the zeroth index won't be used as the index of LISArr represents
//the length of the longest subsequence
vector<int>LISArr;
int lastIndex;
//return the index of the array where item can be placed
//first is the index where to start
//last is the index where to end
int binarySearchIndices(vector<int> arr,int item)
{
//check the boundaries first
if (item < arr[LISArr[1]])
return 1;
if (item > arr[LISArr[lastIndex]])
return lastIndex+1;
int first = 1; //index
int last = lastIndex; //index
int mid = (first+last)/2;
bool found = false;
while (!found && first<=last)
{
cout.flush();
if (item<arr[LISArr[mid]])
last = mid-1;
else if(item>arr[LISArr[mid]])
first = mid+1;
else found = true;
mid = (first+last)/2;
}
if (item>arr[LISArr[mid]])
mid = mid+1;
return mid;
}
public:
//function implements the (nlog n) solution
int LIS(vector<int> arr)
{
int i,ind;
//handle an exception first thing
if (arr.size()==0)
return 0;
LISArr.resize(arr.size()+1,0);
LISArr[1] = 0; //arr[0] is subsequence of length 1
lastIndex = 1; //this is the index of the longet sequence found so far
for (i=1;i<arr.size();++i)
{
ind = binarySearchIndices(arr,arr[i]);
LISArr[ind] = i;
if (ind>lastIndex) //inserting at end
lastIndex = ind;
}
return lastIndex; //this is LIS
}
};
int main()
{
int arr[] = {5, 15 ,8, 7, 4, 10, 20, 19, 7, 25, 29, 11 };
vector <int> myArray(sizeof(arr)/sizeof(arr[0]),0);
for (int i=0;i<myArray.size();++i)
{
myArray[i] = arr[i];
}
LISsolveDP lisDP;
LISsolveFast lisFast;
int result = lisDP.LIS(myArray);
cout << "\n *** result from DP = " << result << "\n";
result = lisFast.LIS(myArray);
cout << "\n *** result from fast method = " << result << "\n";
}
Эффективный алгоритм запуска LIS
LIS с использованием динамического программирования по-прежнему требует O(n^2) вычислений. Можете ли вы найти улучшенный алгоритм, использующий O(n log n) время?
Чтобы понять, как сделать поиск LIS более эффективным, давайте сначала рассмотрим двоичный поиск. Мы можем сократить время вычислений, используя тот факт, что при использовании двоичного поиска требуется O(log n) time to search for an item in a sorted array.
Возвращаясь к поиску _41 _ - мы снова будем использовать промежуточный массив с именем LISArray. Давайте определим его цель в этом случае и выделим несколько важных моментов:
- Мы будем использовать
LISArrayдля хранения индексов входного массиваarr. - Мы также будем использовать
LISArrayдля отслеживания самой длинной найденной подпоследовательности. LISArray[j]:LISArray[j]будет отображаться на индекс наименьшего элемента изarr, который является последним элементом для подпоследовательности длины j.arr[LISArray[j]]: Конечный элемент подпоследовательности длиныj.Size of LISArray[j] = (Size of arr)+ 1, посколькуLISArr[j]содержит информацию о подпоследовательности длины j, индексы начинаются с нуля, поэтому нам нужен дополнительный элемент для хранения максимально возможной длины.LISArray[0]не используется.- Максимальный индекс LISArray может быть
(Size of arr).
Назначение массива
Как только мы поймем назначение массива LISArray, сам алгоритм будет довольно легко понять. В приведенных ниже примерах индексы LISArray являются результатом сканирования всего входного arr. Обратите внимание, что в индексе j он сохраняет результат элемента smallest во всем массиве, который встречается в end of a subsequence of length j.
Это интересно, потому что обратите внимание на следующее;
LISArray: {3, 4, 8}
arr[LISArray[i]] = 1, 6, 8 // (for i=1..2)
Поэтому важно отметить, что LISArray хранит индексы элементов входного массива в отсортированном порядке!
Следовательно, верно следующее:
arr[LISArray[1]] < arr[LISArray[2]] < arr[LISArray[3]] < arr[LISArray[4]] ...
arr[LISArray[j]] < arr[LISArray[j+1]]
Готов к псевдокоду
Вооружившись этими знаниями, мы готовы создать псевдокод для алгоритма, который эффективно решает LIS.
Все, что нам нужно сделать, это просканировать элементы arr один за другим и найти их место в LISArray. Поскольку LISArray хранит индексы элементов входного массива в sorted order, мы можем использовать binary search, чтобы найти место arr[i] в LISArray.
В приведенном ниже примере показано, как LISArray заполняется один за другим, если задан элемент arr. Нам также необходимо отслеживать последний заполненный индекс LISArray. Мы добавляем новый элемент в LISArray только тогда, когда следующий элемент arr выше, чем все элементы, которые были добавлены ранее.
Окончательный псевдокод приведен ниже. Обратите внимание, что алгоритм просматривает каждый элемент arr ровно один раз (n элементов проверяется один раз) и находит свое место в LISArray с помощью двоичного поиска (O(log n) время). Следовательно, общая временная сложность этого алгоритма составляет O(n log n).
Routine: LISFast
Input: arr of length n
Output: Largest increasing subsequence within arr
Intermediate storage: LISArray of size (n+1), initialized to zero
1. lastIndex = 1
2. LISArr[lastIndex] = 0
3. for i=1..n
a. ind = binary search for index position in LISArr for arr[i]
b. LISArr[ind] = i
c. if (ind > lastIndex)
lastIndex = ind
4. return lastIndex
Теперь вы можете написать эффективный код для поиска LIS за O(n log(n)) время, используя примеры и псевдокод.
