最长增长子串问题是一个基本的、常见的小问题，但该问题的求解方法并不明显，为了得到良好的算法，需要更深入的思考和更好的算法策略。 由于这个问题可以运用学到的基本算法分析和设计的方法和思想，可以锻炼设计更复杂算法的思维，所以我对这个问题进行了更深入的分析和思考，得到了一些复杂度不同的算法，并给出了分析和证明。
一.最长增长子序列问题的说明
设L=为n个不同实数的序列，l的递增部分序列是这样的部分序列Lin=。 在此，k1
第二种算法是转换为LCS问题求解
假设序列X=是相对于序列L=按升序排序的序列。 很明显，x和l的最长共同部分序列是l的最长增加部分序列。 这样，将求出最长的增加部分列的问题变换为求出最长的共同部分列的问题LCS。
最长公共子串问题可以用动态规划的算法求解。 设Li=、Xj=，分别为l和x的子串。 将C[i，j]作为Li和Xj的最长公共子串的长度。 有以下递归方程。
这可以用时间复杂度为o(n2 )的算法求解，但该算法在课堂上讲过，具体代码在此省略。 求最长增加子序列的算法的时间复杂度是用于排序的o[nlogn]的时间加上求LCS的O(n2的时间，算法的最差时间复杂度为o[nlogn] o[n2]=o[n2]
三、第二种算法：动态规划法
设f(I )表示以l中的ai为最终要素的最长增加子序列的长度。 有以下递归方程。
此递归方程意味着，在计算以ai为最终元素的最长递增子串时，将找到所有编号在l之前小于ai的元素aj，即j
公共语音lis (浮动[ ] l ) ) ) ) ) ) ) ) ) ) ) ) )。
{int n=L.length； int[] f=new int[n]； 为了保存//f(I )的值
f[0]=1； //以第a1为最后要素的最长增量部分序列的长度为1；
for(intI=1； I
{
f[i]=1； //f[i]的最小值为1；
for(intj=0； Jj
(({if(L[J]F[I]-1 ) ) ) ) ) ) ) ) 652 )
f[i]=f[j] 1； 更新f[i]的值。
}
}
system.out.println(f[n-1]；
}
最长升序子序列1---求出最长公共子序列的长度：
给出长度n的数组，找到最长单调的自增子序列(虽然不一定连续，但顺序不能混乱) )。
例如，如果给出长度为8的序列a{1、3、5、2、4、6、7、8}，则其最长的单调递增子序列为{1、2、4、6、7、8}，长度为6。
输入说明：
第一行包含表示测试数据集数量的整数t。
对于每组测试数据：
N-数组长度
(a1 a2 . an (需要计算的数组) () ) ) ) ) ) ) ) ) ) ) ) 652 ) ) ) )
保修：
1=n=3000，0=ai=max _ int。
输出说明：
对于每组数据，输出表示最长增量子序列长度的整数。
输入示例：
2
7
89 256 78 1 46 78 8
5
6 4 8 2 17
解决问题的思路：采用动态规划的方法求解。 如下。
数组数组数组
ai
89
256
78
1
46
78
8
长度列表
是len(AI )
1
2
1
1
2
3
2
import java.util.*； public class main { publicstaticvoidmain (字符串[ ] args ) }
scanners can=new scanner (system.in )； int T=scan.nextInt (； //system.out.println(t；
for(intI=0； I
int[] num=new int[N]； for(intj=0； Jj
num[j]=scan.nextInt (；
}
系统. out.println (lengthofmaxsubincreasearray (num，n ) )；
}
} publicstaticintlengthofmaxsubincreasearray (int [ ] array，intn ) if ) n==1) {return 1；
(}int maxLen=0； int[] list=new int[n]； for(intI=0； I
list[i]=1； for(intj=0； jlist[i] ) {
list[i]=list[j] 1；
}
}
}for(intI=0； imaxLen )
米
axLen=list[i];}returnmaxLen;
}
}
最长递增子序列2----求最长公共子序列的第一组序列：
给定一个长度为N的数组，找出一个最长的单调自增子序列(不一定连续，但是顺序不能乱)
例如：给定一个长度为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){
Scanner scan= newScanner(System.in);int T =scan.nextInt();//System.out.println(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 maxSubIncreaseArray(int[] array, intn){int[] list = new int[n];
ArrayList> res = new ArrayList>();
ArrayList tmp = new ArrayList();int 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;jlist[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);
}
}