问题描述
对于一串数A={a1a2a3…an}，它的子序列为S={s1s2s3…sn}，满足{s1<s2<s3<…<sm}。求A的最长子序列的长度。
动态规划法
算法描述：
设数串的长度为n，L[i]为以第i个数为末尾的最长上升子序列的长度，a[i]为数串的第i个数。
L[i]的计算方法为：从前i-1个数中找出满足a[j]<a[i]（1<=j<i）条件的最大的L[j]，L[i]等于L[j]+1。
动态规划表达式：
代码实现：
int LIS(int a[], int n)
{
int len[MAXSIZE];
int i, j;
int maxlen = ;
//计算以第i个数为结尾的最长上升子序列的长度
for (i = ; i <= n; i++)
{
len[i] = ;
//从前i-1个数中找出满足a[j]<a[i]（1<=j<i）条件的最大的L[j]
for (j = i-; j >= ; j--)
{
if (a[j] < a[i] && len[j] > len[i])
{
len[i] = len[j];
}
}
len[i]++; if (len[i] > maxlen)
{
maxlen = len[i];
}
}
return maxlen;
}
上述算法的时间复杂度为O(n2)。
改进算法：
在从前i-1个数中找出满足a[j]<a[i]（1<=j<i）条件的最大的L[j]的时间复杂度为O(n)，这里采用二分查找的方法对它进行优化，使其复杂度降为O(nlogn)。
增设一个m[]数组，m[x]存放长度为x的最长上升子序列的最小末尾数。例：m[3] = 17表示长度为3的最长上升子序列的最小末尾数为17。
由于子序列是上升的，所以m数组中的元素有一个性质，当x<y时，m[x]<m[y]，利用这个性质来使用二分查找。
设m数组所存储的最长上升子序列的长度为k，当前计算的数为第i个
如果a[i]>m[k]，则m[++k]=a[i]；
否则在m[1~k]内二分查找小于（等于）a[i]的最大值的位置p，m[p]=a[i]。
代码实现：
int BSearch(int a[], int n, int t)
{
int low = ;
int high = n; while (low <= high)
{
int mid = (low + high) / ;
if (t == a[mid])
{
return mid;
}
else if (t > a[mid])
{
low = mid + ;
}
else
{
high = mid - ;
}
}
return low;
} int LIS_BSearch(int a[], int m[], int n)
{
int maxlen = ; //最长上升子序列的长度
m[maxlen] = a[]; int i;
for (i = ; i <= n; i++)
{
if (a[i] > m[maxlen])
{
m[++maxlen] = a[i];
}
else
{
//返回小于a[i]的最大值的位置p
int p = BSearch(m, maxlen, a[i]);
m[p] = a[i];
}
}
return maxlen;
}
改进后的算法时间复杂度为O(nlogn)。