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);
}
}
设 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 的元素结尾 .
如果 X > S 中的最后一个元素，则 parent[indexX] = indexLastElement . 这意味着最新元素的父元素是最后一个元素 . 我们只是将 X 添加到 S 的末尾 .
否则找到 S 中最小元素的索引，即 >= 而不是 X ，并将其更改为 X . 这里 parent[indexX] = S[index - 1] .
0
Petar Minchev的解释帮助我解决了问题，但我很难解析所有内容，因此我使用过度描述性的变量名称和大量注释进行了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
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)
/**
** 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();
}
}
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]+" ");
}
}
9
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)
14 回答
这是另一个O（n ^ 2）JAVA实现 . 没有递归/ memoization来生成实际的子序列 . 只是一个字符串数组，用于存储每个阶段的实际LIS，以及一个数组，用于存储每个元素的LIS长度 . 非常简单 . 看一看：
行动守则：http://ideone.com/sBiOQx
好的，我将首先描述最简单的解决方案，即O（N ^ 2），其中N是集合的大小 . 还有一个O（N log N）解决方案，我也将对此进行描述 . 在Efficient algorithms部分查看here .
我将假设数组的索引从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]获取最大值 .我使用数组
prev以后能够找到实际的序列，而不仅仅是它的长度 . 只需使用prev[bestEnd]在循环中从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脚步：
所以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是：
现在重要的是 - 我们如何更新父数组？有两种选择：
如果
X>S中的最后一个元素，则parent[indexX] = indexLastElement. 这意味着最新元素的父元素是最后一个元素 . 我们只是将X添加到S的末尾 .否则找到
S中最小元素的索引，即>=而不是X，并将其更改为X. 这里parent[indexX] = S[index - 1].Petar Minchev的解释帮助我解决了问题，但我很难解析所有内容，因此我使用过度描述性的变量名称和大量注释进行了Python实现 . 我做了一个天真的递归解决方案，O（n ^ 2）解决方案和O（n log n）解决方案 .
我希望它有助于清理算法！
递归解决方案
O（n ^ 2）动态编程解决方案
O（n log n）动态编程解决方案
谈到DP解决方案，我发现令人惊讶的是没有人提到LIS可以减少到LCS的事实 . 您需要做的就是对原始序列的副本进行排序，删除所有重复项并对其进行LCS . 在伪代码中它是：
用Go编写的完整实现 . 如果不需要重建解决方案，则无需维护整个n ^ 2 DP矩阵 .
以下C实现还包括一些使用名为
prev的数组构建实际最长增加子序列的代码 .没有堆栈的实现只是反向向量
以下是从动态编程的角度评估问题的三个步骤：
重复定义：maxLength（i）== 1 maxLength（j）其中0 <j <i和array [i]> array [j]
重复参数边界：可能有0到i - 作为参数传递的1个子序列
评估顺序：由于它正在增加子序列，因此必须从0到n进行评估
如果我们在索引处以序列{0,8,2,3,7,9}为例：
[0]我们将得到子序列{0}作为基本情况
[1]我们有1个新的子序列{0,8}
[2]试图通过将索引2处的元素添加到现有子序列来评估两个新序列{0,8,2}和{0,2} - 只有一个是有效的，因此添加第三个可能的序列{0,2}仅参数列表...
这是工作的C 11代码：
这是O（n ^ 2）算法的Scala实现：
这可以使用动态编程在O（n ^ 2）中求解 . 相同的Python代码如下： -
输入：
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的最长增加子序列长度 .
这里是java O（nlogn）实现
这是O（n ^ 2）中的Java实现 . 我只是没有使用二进制搜索来找到S中的最小元素，即> = X.我只使用了for循环 . 使用二进制搜索会使复杂度达到O（n logn）
使用数组元素检查java中的代码，以获取最长的子序列
http://ideone.com/Nd2eba
这可以使用动态编程在O（n ^ 2）中求解 .
按顺序处理输入元素并维护每个元素的元组列表 . 每个元组（A，B），对于元素i将表示，A =在i处结束的最长增长子序列的长度，B =在列表[i]处结束的最长增长子序列中的列表[i]的前任的索引] .
从元素1开始，元素1的元组列表对于元素i将是[（1,0）]，扫描列表0..i并找到元素列表[k]，使得列表[k] <list [i] ，元素i的A值，Ai为Ak 1，Bi为k . 如果有多个这样的元素，请将它们添加到元素i的元组列表中 .
最后，找到最大值为A（LIS的长度以元素结尾）的所有元素，并使用元组返回以获取列表 .
我在http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799分享了相同的代码
O（n ^ 2）java实现：
即使有一种方法可以在O（nlogn）时间内解决这个问题（这在O（n ^ 2）时间内得到解决），但这种方式仍然提供了动态编程方法，这也很好 .