一、最长递增子序列问题的描述
设
是n个不同的实数的序列，L的递增子序列是这样一个序列
，其中
且
。求最大m值。
二、第一种算法：转化为LCS问题求解
设序列
是对序列
按递增排好序的序列。那么，显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。
最长公共子序列问题可用动态规划求解。设
，
分另为L和X的子序列。令
为
与
的最长公共子序列的长度。有如下递推方程：
这可以用时间复杂度为
的算法求解。又排序算法复杂度为
，可得总复杂度为
。
三、第二种算法：动态规划
设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程：
这个递推方程的意思是，在求以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j<i且aj<ai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
算法复杂度为
。这个算法的最坏时间复杂度与第一种算法的阶是相同的。但这个算法没有排序时间，优于第一种算法。
四、对第二种算法的改进
在第二种算法中，在计算每一个f(i)时，都要找出最大的f(j)(j<i)来，由于f(j)没有顺序，只能顺序查找满足
最大的f(j)，如果能将让f(j)有序，就可以使用二分查找，这样算法的时间复杂度就可能降到
。于是想到用一个数组B来存储“子序列的”最大递增子序列的最末元素，即有：
在计算f(i)时，在数组B中用二分查找法找到满足j<i且
的最大的
，并将B[f[j]+1]置为ai。下面先写出代码，再证明算法的证明性。用Java实现的代码如下：
lis1(float[] L)
{
int n = L.length;
float[] B = new float[n+1];//数组B；
B[0]=-10000;//把B[0]设为最小，假设任何输入都大于-10000；
B[1]=L[0];//初始时，最大递增子序列长度为1的最末元素为a1
int Len = 1;//Len为当前最大递增子序列长度，初始化为1；
int p,r,m;//p,r,m分别为二分查找的上界，下界和中点；
for(int i = 1;i<n;i++)
{
p=0;r=Len;
while(p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列；
{
m = (p+r)/2;
if(B[m]<L[i]) p = m+1;
else r = m-1;
}
B[p] = L[i];//将长度为p的最大递增子序列的当前最末元素置为ai+1;
if(p>Len) Len++;//更新当前最大递增子序列长度；
}
System.out.println(Len);
}
现在来证明这个算法为什么是正确的。要使算法正确只须证如下命题：
命题1：每一次循环结束数组B中元素总是按递增顺序排列的。
证明：用数学归纳法，对循环次数ｉ进行归纳。
当i=0时，即程序还没进入循环时，命题显然成立。
设i<k时命题成立，当i=k时，假设存在
，
，因为第i次循环之前数组B是递增的，因此第i次循环时B[j1]或B[j2]必有一个更新，假设B[j1]被更新为元素ai+1，由于ai+1=B[j1]> B[j2]，按算法ai+1应更新B[j2]才对，因此产生矛盾；假设B[j2]被更新，设更新前的元素为s,更新后的元素为ai+1，则由算法可知第i次循环前有B[j2]＝s< ai+1< B[j1]，这与归纳假设矛盾。命题得证。
命题2：B[c]中存储的元素是当前所有最长递增子序列长度为c的序列中，最小的最末元素，即设当前循环次数为i，有B[c]={aj| f(k)=f(j)=c∧k,j≤i+1→aj≤ak}(f(i)为与第二种算法中的f(i)含义相同)。
证明：程序中每次用元素ai更新B[c]时(c=f(i))，设B[c]原来的值为s，则必有ai<s，不然ai就能接在s的后面形成长度为c+1的最长递增子序列，而更新B[c+1]而不是B[c]了。所以B[c]中存放的总是当前长度为ｃ的最长递增子序列中，最小的最末元素。
命题3：设第i次循环后得到的p为p(i+1)，那么p(i)为以元素ai为最末元素的最长递增子序列的长度。
证明：只须证p(i)等于第二种算法中的f(i)。显然一定有p(i)<＝f(i)。假设p(i)<f(i)，那么有两种情况，第一种情况是由二分查找法找到的p(i)不是数组B中能让ai接在后面成为新的最长递增子序列的最大的元素，由命题1和二分查找的方法可知，这是不可能的；第二种情况是能让ai接在后面形成长于p(i)的最长递增子序列的元素不在数组B中，由命题2可知，这是不可能的，因为B[c]中存放的是最末元素最小的长度为c的最长递增子序列的最末元素，若ai能接在长度为L(L> p(i))的最长递增子序列后面，就应该能接在B[L]后面，那么就应该有p(i)=L,与L> p(i)矛盾。因此一定有p(i)＝f(i)，命题得证。
算法的循环次数为n，每次循环二分查找用时logn，所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进。