我有一组整数。我想用动态规划的方法求出这个集合的最长递增子序列。
好的，我先描述最简单的解也就是O(N²)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是为了以后能够找到实际的序列，而不仅仅是它的长度。只需在循环中使用prev[bestEnd]从bestEnd递归返回。-1值是停止的标志。
好了，现在来看更有效的O(nlog 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]是LIS中索引为i的元素的前身，该元素以索引为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。这意味着最新元素的父元素是最后一个元素。我们只是在S的末尾加上X。 否则，找到S中最小元素的索引>= than X，并将其更改为X。这里parent[indexX] = S[index - 1]。
下面的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;
}
Petar Minchev的解释帮助我理清了事情，但我很难解析所有内容，所以我做了一个带有过度描述性变量名和大量注释的Python实现。我做了一个简单的递归解，O(n²)解，和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²)动态规划解
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
下面是从动态规划的角度评估问题的三个步骤:
递归定义:maxLength(i) == 1 + maxLength(j) where 0 < j < i and array[i] > array[j] 递归参数边界:可能有0到i - 1个子序列作为参数传递 求值顺序:由于是递增子序列，所以要从0求值到n
如果我们以序列{0,8,2,3,7,9}为例，at index:
我们会得到子序列{0}作为基本情况 [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;
}
这可以用动态规划在O(n²)中解决。同样的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的最长递增子序列长度。
下面是O(n^2)算法的Scala实现:
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)))
}
}
这是一个O(n²)的Java实现。我只是没有使用二分搜索来找到S中最小的元素，它是>= than 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));
}
这是另一个O(n²)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
这里是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);
}
}
//可以使用TreeSet
用Java签出包含数组元素的最长递增子序列的代码
http://ideone.com/Nd2eba
/**
** 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();
}
}
这可以用动态规划在O(n²)中解决。
按顺序处理输入元素，并为每个元素维护一个元组列表。每个元组(A,B)，对于i将表示的元素，A =以i结尾的最长递增子序列的长度，B =以列表[i]结尾的最长递增子序列中列表[i]的前身的索引。
从元素1开始，元素1的元组列表为[(1,0)] 对于元素i，扫描列表0..i，找到元素list[k]，使得list[k] < list[i]，元素i的A值，Ai为Ak + 1, Bi为k。如果有多个这样的元素，将它们添加到元素i的元组列表中。
最后，找到所有最大值为A (LIS以element结尾的长度)的元素，并使用元组回溯以获得列表。
我已经在http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799上分享了相同的代码
说到DP solution，我发现很奇怪的是没有人提到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]
}
O(n²)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]+" ");
}
}
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²)时间内解决)但这种方法仍然提供了动态规划方法，这也是很好的。
这是我的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)
c++中最简单的LIS解决方案，具有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
最长递增子序列(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+" ");
}
}
}
我已经在java中使用动态编程和记忆实现了LIS。随着代码，我做了复杂性计算，即为什么它是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
求最长递增子序列的O(NLog(N))方法 让我们维护一个数组，其中第i个元素是一个大小为i的子序列可以结束的最小的数字。
我故意避免进一步的细节，因为投票最多的答案已经解释了它，但这种技术最终导致使用set数据结构的整洁实现(至少在c++中)。
下面是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;
}
求最长递增子序列(LIS)的O(NLog(N))递归DP方法
解释
该算法涉及创建节点格式为(a,b)的树。
A表示到目前为止我们考虑添加到有效子序列的下一个元素。
B表示剩余子数组的起始索引，如果a被添加到目前为止我们所拥有的子数组的末尾，则下一个决策将从该子数组开始。
算法
We start with an invalid root (INT_MIN,0), pointing at index zero of the array since subsequence is empty at this point, i.e. b = 0. Base Case: return 1 if b >= array.length. Loop through all the elements in the array from the b index to the end of the array, i.e i = b ... array.length-1. i) If an element, array[i] is greater than the current a, it is qualified to be considered as one of the elements to be appended to the subsequence we have so far. ii) Recurse into the node (array[i],b+1), where a is the element we encountered in 2(i) which is qualified to be appended to the subsequence we have so far. And b+1 is the next index of the array to be considered. iii) Return the max length obtained by looping through i = b ... array.length. In a case where a is bigger than any other element from i = b to array.length, return 1. Compute the level of the tree built as level. Finally, level - 1 is the desired LIS. That is the number of edges in the longest path of the tree.
注意:算法的记忆部分被省略了，因为它是从树中清除的。
随便举个例子 标记为x的节点从DB内存值中获取。
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;
}
