最长递增子序列 java_最长递增子序列问题---动态规划
最长递增子序列问题是一个经典的、基础性较强的简单问题。然而，解决这一问题的方法并不显然易懂，需要深入思考并具备扎实的算法基础才能设计出高效的解决方案。由于该问题能够运用所学的基本算法分析与设计方法与思想来进行解决，并且能够有效锻炼设计较为复杂的算法思维能力，在我的研究中对此问题进行了深入分析与思考，并得出了多种不同复杂度的解决方案，并对其进行了详细分析并进行了证明。
一，最长递增子序列问题的描述
令L是一个由n个互不相同的实数组成的序列表示，则称该序列为一个单调递增的数列Li_n满足Li_1 < Li_2 < … < Li_k（其中k ≤ n）。
二，第一种算法：转化为LCS问题求解
我们设定一个有序序列X等于另一个有序排列L按照升序重新排列后的结果。显然地，在此情形下，则X与L之间的最长公共子排列即代表了L自身的最长递增排列。这样一来，则将寻找原始有序排列L的最大长度递增排列问题成功地转化为寻找两个特定有序排列之间最大长度共同排列的问题（即问题LCSS）。
最长公共子序列问题可通过动态规划算法得以解决。令Li和Xj分别表示序列L和X的子序列，并令C[i,j]表示Li与Xj之间的最长公共子序列长度。以下为计算C[i,j]所遵循的递推关系式：
该问题可用时间复杂度为O(n^2)的算法来解决。因该算法在课堂上已讲解过,此处省略代码部分。对于求最长递增子序列这一算法,其时间复杂度等于排序所需的时间（即O(n\log n)）加上求最长公共子序列所需的时间（即O(n^2)），因此其最坏情况下的时间复杂度为 O(n^2)
三，第二种算法：动态规划法
定义f(i)为L中以a_i结尾的最长递增子序列的长度，则可得如下的递推公式：
该递推方程所表达的意思是，在计算以ai为末尾元素的最大递增子序列时，请找出所有满足j属于集合L且j < ai的所有下标j对应的元素aj，并将这些aj放入对应的位置。
public void lis(float[] L)
{int n =L.length;int[] f = new int[n];//用于存放f(i)值；
f[0]=1;//以第a1为末元素的最长递增子序列长度为1；
for(int i = 1;i
{
f[i]=1;//f[i]的最小值为1；
for(int j=0;j __
{if(L[j]f[i]-1)
f[i]=f[j]+1;//更新f[i]的值。
}
}
System.out.println(f[n-1]);
}
最长递增子序列1---求最长公共子序列的长度：
对于长度为N的一个数组A来说，请确定该数组中的最长单调递增子序列。此序列无需连续元素但必须保持原有的顺序。
例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6.
输入描述:
第一行包含一个整数T，代表测试数据组数。
对于每组测试数据：
N-数组的长度
a1 a2 ... an (需要计算的数组)
保证：
1<=N<=3000,0<=ai<=MAX_INT.
输出描述:
对于每组数据，输出一个整数，代表最长递增子序列的长度。
输入例子:
2
7
89 256 78 1 46 78 8
5
6 4 8 2 17
解题思路：采用动态规划的方法来解，如下：
数组array
ai
89
256
78
1
46
78
8
长度list
len(ai)
1
2
1
1
2
3
2
import java.util.*;public classMain{public static voidmain(String[] args){
Input tool scan = instantiation of $I/O stream;
integer variable named count = scan.nextInt();
//System.out.println(count);
for(int i=0;i
int[] num = new int[N];for(int j=0;j
num[j]=scan.nextInt();
}
System.out.println(lengthOfMaxSubIncreaseArray(num, N));
}
说明
}int maxLen = 0;int[] list = new int[n];for(int i=0;i
list[i]=1;for(int j=0;j list[i]){
list[i]= list[j]+1;
}
}
}for(int i=0;imaxLen)
maxLen=list[i];
}returnmaxLen;
}
}
最长递增子序列2----求最长公共子序列的第一组序列：
设有一个长度为N的数组A（记作A[1..n]），寻找其最大的严格递增子序列S（记作S[1..m]），其中m的最大值即为所求解。
例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6.
输入描述:
第一行包含一个整数T，代表测试数据组数。
对于每组测试数据：
N-数组的长度
a1 a2 ... an (需要计算的数组)
保证：
1<=N<=3000,0<=ai<=MAX_INT.
输出描述:
对于每组数据，输出一个整数序列，代表最长递增子序列。
若有多组最长上升子序列，输出第一组。
保证：1<=T<=20,1<=N<=3000,0<=ai<=MAX_INT.
输入例子:
2
7
89 256 78 1 46 78 8
5
6 4 8 2 17
输出例子:
1 46 78
6 8 17
import java.util.*;public classMain{public static voidmain(String[] args){
创建一个名为scan的Scanner对象，并将其与标准输入流关联。
读取用户输入并将其转换为整数类型存入变量T中。
//打印变量T的值。
for(int i=0;i
int[] num = new int[N];for(int j=0;j
num[j]=scan.nextInt();
}
System.out.println(maxSubIncreaseArray(num, N));
}
public static ArrayList maxSubEnhanceArray(int[] array, int n) { int[] list = new int[n]; }
ArrayList> res = new ArrayList>();
创建一个新的ArrayList实例用于存储临时数据。\n\nint index = -1;//其中index变量初始化为-1用于标识当前元素之前第一个递增子序列的位置
int maxIndex = 0;//用于标记该序列的最长递增子序列的位置
int max = Integer.MIN_VALUE;//最长递增子序列的长度
list[0] = 1; //该列表用以表示包含当前项在内的前半部分的长递增子序列的长度
tmp.add(array[0]);
res.add(tmp);for(int i=1;i
index= -1;
tmp= new ArrayList();for(int j=0;j list[i]){
list[i]=list[j];
index=j;
}
}++list[i];if(index>-1)
tmp.addAll(res.get(index));
tmp.add(array[i]);
res.add(tmp);if(list[i]>max){
max=list[i];
maxIndex=i;
}
}returnres.get(maxIndex);
}
}