刚刚研究了一下。我有个问题……
就是改良版本的LIS，我的资料说它求出来的D并不是题目要求的子序列。但是我产生的例子里面，它恰恰是一个满足要求的子序列啊……这是巧合，还是说D的结果可以当作一个满足要求的子序列？
如果是巧合，那在改良版本的LIS中，如何求得满足要求的子序列？
程序代码：
/*
* LIS - Longest Increasing Subsequence
*/
#include <stdlib.h>
/*
* O(n^2) 方法
* a内存输入的数字
* 返回最长上升子序列的长度
* b用来返回最长递增子序列的值。
*/
int lis_dp(const int *a, int *b, size_t len)
{
int i, j, dmax, bmax;
int *d = (int*)malloc(len * sizeof(int));
/*
* 从0开始分析，则对于a[0]来说，最长的上升子序列长度就是
* 1，即a[0]本身。那么对于a[0]和 a[1]来说，则分析如下：
* - 如果a[0] <= a[1] 则最长子序列长度为 a[0]的长度+1
* - 如果a[0] > a[1] 则最长子序列的长度为 a[0]和a[1]中
* 比较长的那个。
*
* 我们用d[n] (0<n<=len)来保存a[n]的最长子序列的值。那么
* 很轻易就可以得到d[n]的状态转移式：
* - d[0] = 1
* - d[n] = max{1, d[i]+1}, 其中i=n+1,n+2,...,len-1
*
* 不过，下面的代码采取了逆推的方式，因为这样可以马上得
* 到最长递增序列的第一个值，从而很轻松就可以顺推得到整
* 个序列，而如果顺推的话，那得到整个序列就需要开另外一
* 个数组来逆推。这样很麻烦。
*/
bmax = b[len-1] = len - 1;
dmax = d[len-1] = 1;
for (i = len - 2; i >= 0; i--)
{
b[i] = i;
d[i] = 0;
for (j = i; j < len; j++)
{
if (a[i] < a[j] && d[i] < d[j] + 1)
{
b[i] = j;
d[i] = d[j] + 1;
}
}
if (d[i] > dmax)
{
bmax = i;
dmax = d[i];
}
}
free(d);
for (i = 0; bmax != b[bmax]; i++)
{
j = bmax;
bmax = b[bmax];
b[i] = a[j];
}
b[i] = a[bmax];
return dmax;
}
/*
* O(nlgn)方法
* 参数同上
*/
int lis_improve(const int *a, int *b, size_t len)
{
int i, blast;
/*
* 首先我们考虑经典的计算LIS的方法。
* 对于每个a[i]，我们可以求出一个相应的f[i]（即上面的
* d[i]），这个f[i]取决于i之前的每个f[n](0<=n<i)的最大值
* 。那么我们考虑一下这种情况，如果在i之前有x和y，满足：
* - x < y < i; a[x] < a[y] < a[i]; f[x] = f[y]且最大
* 那么，因为f[x] = f[y]，我们应该选择x还是y作为f[i]的选
* 取值呢？显然选择x比y要好。因为a[x]要大于a[y]，这样选
* 择了x，使得x和i的距离最大化了，如果这段距离中，有
* a[z] 满足a[x] < a[z] < a[y]，那么与选择a[y]相比，将会
* 得到更长的上升子序列（当然这种情况下，a[z]本身的 f[z]
* 会大于a[x]和a[y]，但是这是在单独扫描的情况下，下面我
* 们会看到另一种完全不需要求F[i]的方法）。
*
* 那么，我们其实可以对于每个f[i]进行分类。我们只需要保
* 留满足f[i]=k的所有A[i]总的最小的那个值就够了。假设
* D[j]记录这个最小值，则D[j]=min{A[i]}(F[i]=k)。
*
* 因为f[i]是一直上升的。所以其D[j]也应该是一直上升的。
* 从而D是一个有序的序列。利用这个序列，我们可以得到另外
* 一种计算最长递增子序列的方法。同样设当前要判断的节点
* 为A[i]，假设这时D序列的长度为len。则直接判断A[i]和
* D[len-1]。如果A[i]比较大，证明A[i]至少比我们之前找到
* 的所有有可能出现在最长递增子序列里面的值要大。显然这
* 时候最长子序列的长度应该被扩展一个。因此将A[i]加在D的
* 后面，同时len加一。然而。如果A[i]比D[len-1]要小。则很
* 显然，这个A[i]无法为扩展子序列提供任何“帮助”。但它本
* 身仍然可能成为新的最长子序列中的一员。怎么办呢？我们
* 在D中寻找这样一个位置x，使得D[x] < A[i] <= D[x+1]，显
* 然，因为A小于D[x+1]，根据上面的分析，相对于D[x+1]，使
* 用A[i]能帮助我们得到更长的递增子序列。所以我们用A[i]
* 来代替D[x+1]的位置。
*
* 一直重复这个过程，直到到最后的A[len-1]，这样，len就是
* 我们的最长递增子序列的长度了。
*
* 对于这个方法。如果查找的时候使用顺序查找。显然复杂度
* 仍然为O(n^2)不变。但是考虑到D为单调上升序列。那么只需
* 要在D上使用二分查找。则复杂度会提高到O(nlgn)，这是一
* 个相当大的提高。但前提是二分查找的设计合理高效。
*
* 下面的实现中。使用的是b的最后一个元素的位置blast，而
* 不是b序列的长度，只是效率上的考虑，本身没什么关系的。
*/
b[0] = a[0];
blast = 0;
for (i = 1; i < len; i++)
{
if (a[i] < b[blast])
{
size_t begin = 0, end = blast;
while (begin < end)
{
size_t middle = (begin + end) >> 1;
if (b[middle] < a[i])
begin = middle + 1;
else
end = middle - 1;
}
b[end + (b[end] < a[i])] = a[i];
}
else
b[++blast] = a[i];
}
return blast + 1;
}
#include <stdio.h>
int main(void)
{
int i, res;
int a[] = {1, 4, 7, 20, 2, 11, 5, 13, 6, 10}, b[10];
printf("lis_dp: %d\n", res = lis_dp(a, b, 10));
for (i = 0; i < res; i++)
printf("%d ", b[i]);
printf("\nlis_improve: %d\n", res = lis_improve(a, b, 10));
for (i = 0; i < res; i++)
printf("%d ", b[i]);
printf("\n");
return 0;
}
