LIS算法
LIS（Longest Increasing Subsequence）最长上升(不下降)子序列
转帖
http://hi.baidu.com/format%5Fscut/blog/item/23903aec54b198d32f2e2193.html
有两种算法复杂度为O(n*logn)和O(n^2)
O(n^2)算法分析如下： （a[1]...a[n] 存的都是输入的数）
1、对于a[n]来说，由于它是最后一个数，所以当从a[n]开始查找时，只存在长度为1的不下降子序列；
2、若从a[n-1]开始查找，则存在下面的两种可能性：
（1）若a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n].
（2）若a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。
3、一般若从a[t]开始，此时最长不下降子序列应该是按下列方法求出的：
在a[t+1],a[t+2],...a[n]中，找出一个比a[t]大的且最长的不下降子序列，作为它的后继。
4、为算法上的需要，定义一个数组：
d:array [1..n,1..3] of integer;
d[t,1]表示a[t]
d[t,2]表示从i位置到达n的最长不下降子序列的长度
d[t,3]表示从i位置开始最长不下降子序列的下一个位置
最长不下降子序列的O(n*logn)算法分析如下：
先回顾经典的O(n^2)的动态规划算法，设A[t]表示序列中的第t个数，F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度，初始时设F[t] = 0(t = 1, 2, ..., len(A))。则有动态规划方程：F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。
现在，我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到同样的F[t]值，那么，在最长上升子序列的这个位置中，应该选择A[x]还是应该选择A[y]呢？
很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[t-1]这一段中，如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。
再根据条件(3)，我们会得到一个启示：根据F[]的值进行分类。对于F[]的每一个取值k，我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值，即D[k] = min{A[t]} (F[t] = k)。
注意到D[]的两个特点：
(1)D[k]的值是在整个计算过程中是单调不上升的。
(2)D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A[t] > D[len]，则将A[t]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A[t]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[t]。令k = j + 1，则有D[j] < A[t] <= D[k]，将A[t]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = A[t]。最后，len即为所要求的最长上升子序列的长度。
在上述算法中，若使用朴素的顺序查找在D[1]..D[len]查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来的算法相比没有任何进步。但是由于D[]的特点(2)，我们在D[]中查找时，可以使用二分查找高效地完成，则整个算法的时间复杂度下降为O(nlogn)，有了非常显著的提高。需要注意的是，D[]在算法结束后记录的并不是一个符合题意的最长上升子序列！
这个算法还可以扩展到整个最长子序列系列问题，整个算法的难点在于二分查找的设计，需要非常小心注意。
code by hjin:/*---------------------------------------------------------------------------
File name: fy-0033-最长递增子序列.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 10/11/2007 11:37:19
Environment: WinXPSP2 En Pro + VS2005 v8.0.50727.762
Problem statement:
---------------------------------------------------------------------------
http://yzfy.org/bbs/viewthread.php?tid=101&extra=page%3D1
习题 33：最长递增子序列★★★
问题描述：
所谓子序列，就是在原序列里删掉若干个元素后剩下的序列，以字符串"abcdefg"为例子，去掉bde得到子序列"acfg"
现在的问题是，给你一个数字序列，你要求出它最长的单调递增子序列。
输入：
多组测试数据，每组测试数据第一行是n(1<=n<=10000)，下一行是n个比1e9小的非负整数
输出：
对于每组测试数据输出一行，每行内容是最长的单调递增子序列的长度
样例输入：
5
1 2 4 8 16
5
1 10 4 9 7
9
0 0 0 1 1 1 5 5 5
样例输出：
5
3
3
难度：normal
*/
#define CP_VC6PP
#include <stdio.h>
#define N 10000
int b[N];
int main()
{
int n, j, p, m, r, a;
while(scanf("%d", &n)!=EOF)
{
/**
0. b[1..j] keeps the current longest (strictly) increasing subsequence (LIS).
1. j is the length of the LIS.
O(n lgn) algorithm for LIS:
-----------------------------------------------------------
j:=0
b[0] := INT_MIN
for i:=0 to n-1
If a is larger than the current max in b[0..j]
j := j+1
b[j] := a
else
binary search b[1..j] to find k such that
b[k-1] < a <= b[k]
b[k] := a
return j
-----------------------------------------------------------
*/
j=0;
b[0]=0x80000000;
while(n--)
{
scanf("%d", &a);
if( b[j] < a )
{
++j;
b[j]=a;
}
else
{
p=1;
r=j;
while(p<=r)
{
m=(p+r)>>1;
if(b[m] < a)
{
p=m+1;
}
else if(b[m-1]>=a)
{
r=m-1;
}
else
break;
}
b[m]=a;
}
}
printf("%d
", j);
}
return 0;
}code by wangfangbob:#include <stdio.h>
#define MAX 10000
int main( void )
{
int n, i, j, max, tmp, low, up, mid;
int source[MAX];
int len[MAX];
while ( EOF != scanf( "%d", &n ) )
{
scanf( "%d", source );
len[0] = source[0];
for ( i = 1, max = 0; i < n; ++i )
{
scanf( "%d", source + i );
low = 0, up = max;
while ( low <= up )
{
mid = ( up + low ) >> 1;
len[mid] < source ? low = mid + 1 : up = mid - 1;
}
len[low] = source;
if ( low > max )
{
++max;
}
}
printf( "%d
", max + 1 );
}
return 0;
}O(n*logn)的算法代码写起来很简单，比较难理解哈~不懂的大家下次再交流一下hoho
我的代码是这样子滴~！~笑ing~~~/*---------------------------------------------------------------------------
File name: yzfy_33-最长递增子序列.c
Author: wtthappy (email: wangtingting880818@yahoo.com.cn )
Created on: 11/15/2007
Environment: WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0
Problem statement:
---------------------------------------------------------------------------
http://yzfy.org/bbs/viewthread.php?tid=101&extra=page%3D1
习题 33：最长递增子序列★★★
问题描述：
所谓子序列，就是在原序列里删掉若干个元素后剩下的序列，以字符串"abcdefg"为例子，去掉bde得到子序列"acfg"
现在的问题是，给你一个数字序列，你要求出它最长的单调递增子序列。
输入：
多组测试数据，每组测试数据第一行是n(1<=n<=10000)，下一行是n个比1e9小的非负整数
输出：
对于每组测试数据输出一行，每行内容是最长的单调递增子序列的长度
样例输入：
5
1 2 4 8 16
5
1 10 4 9 7
9
0 0 0 1 1 1 5 5 5
样例输出：
5
3
3
难度：normal
*/
#include <stdio.h>
int main()
{
int array[10000];
int amount; //数据总数
int high,low,middle; //二分查找用到的变量
int top; //栈顶
int number; //读取的数据
int i; //调试用变量，表示数组下标
while ( scanf( "%d", &amount ) != EOF )
{
scanf( "%d", array ); //第一个数字个别处理
low = high = top = 0;
while ( --amount )
{
scanf( "%d", &number );//二分查找覆盖
low = 0; //初始化两端
high = top;
while ( low <= high )
{
middle = ( low+high )/2;
( array[middle] >= number )? ( high = middle-1 ) : ( low = middle+1 ) ;
}
array[low] = number;
if ( low > top ) //如果最大则入栈
{
top = low;
}
/*----------调试----------------------------------------------------------------
for ( i = 0 ; i <= top ; ++i )
{
printf( "%d ", array );
}
printf( "
" );
------------------------------------------------------------------------------*/
}
printf( "%d
", top+1 ); //结果
}
// system( "AUSE" );
return 0;
}
//第一次这样写代码哈哈，仿照hjin .c