单调子序列包含有单调递增子序列和递减子序列,不失一般性,这里只讨论单调递增子序列。首先,从定义上明确我们的问题。给定序列a1, a2, …, an,如果存在满足下列条件的子序列
ai1<=ai2<=…<=aim, (其中i1<i2<…<im)
即称为一个原序列的长度为m的单调递增子序列,那么,现在的问题是我们要找出一个序列的最长的单调递增子序列。
直观上来说,一个序列Sn,它有2n个子序列,枚举所有的子序列,找出其中单调递增的序列,然后返回其中最长的,这样我们的问题就解决了。当然,这个直观的算法在时间上为O(2n*n),它的复杂度增长太快了,所以,我们还应该做得更好一些。
于是,我们换个角度思考。假设我们对Sn排序(递增),得到Sn’。那么,Sn和Sn’的最长公共子序列Cm就是我们要求的最长单调递增子序列(如果你不清楚最长公共子序列的定义,just google it)。为什么?假设Cm’是Sn的最长单调子列,且Cm’!=Cm,
Cm’的长度大于Cm。由于Cm’是递增的,并且Cm’的每一个元素都来自Sn,所以Cm’一定是Sn’的子列,而Cm’又是Sn的子列,所以Cm’是Sn和Sn’的公共子列,故Cm’的长度一定小于Cm,这与假设矛盾,所以Cm是最长单调子列。理论上我们的算法是正确的,复杂度方面,运用动态规划(dynamic
programming)来求解LCS(最长公共子列,Longest-Common-Subsequence),时间上是O(n2),空间上也是O(n2)。于是,对Sn排序需要nlogn的时间,而LCS需要n2,最后,我们的算法时间上是O(n2)。
Cm’的长度大于Cm。由于Cm’是递增的,并且Cm’的每一个元素都来自Sn,所以Cm’一定是Sn’的子列,而Cm’又是Sn的子列,所以Cm’是Sn和Sn’的公共子列,故Cm’的长度一定小于Cm,这与假设矛盾,所以Cm是最长单调子列。理论上我们的算法是正确的,复杂度方面,运用动态规划(dynamic
programming)来求解LCS(最长公共子列,Longest-Common-Subsequence),时间上是O(n2),空间上也是O(n2)。于是,对Sn排序需要nlogn的时间,而LCS需要n2,最后,我们的算法时间上是O(n2)。
可以看到,通过上面的改进,我们的算法效率得到了很大的提升(从指数增长到多项式增长)。不过,程序设计的乐趣就是它会不断地给我们一些惊喜,所以,就此打住不是我们该做的,于是,更好的算法应该是存在的。
对于序列Sn,考虑其长度为i的单调子列(1<=i<=m),这样的子列可能有多个。我们选取这些子列的结尾元素(子列的最后一个元素)的最小值。用Li表示。易知
L1<=L2<=…<=Lm
如果Li>Lj(i<j),那么去掉以Lj结尾的递增子序列的最后j-i个元素,得到一个长度为i的子序列,该序列的结尾元素ak<=Lj<Li,这与Li标识了长度为i的递增子序列的最小结尾元素相矛盾,于是证明了上述结论。现在,我们来寻找Sn对应的L序列,如果我们找到的最大的Li是Lm,那么m就是最大单调子列的长度。下面的方法可以用来维护L。
从左至右扫描Sn,对于每一个ai,它可能
(1) ai<L1,那么L1=ai
(2) ai>=Lm,那么Lm+1=ai,m=m+1 (其中m是当前见到的最大的L下标)
(3) Ls<=ai<Ls+1,那么Ls+1=ai
扫描完成后,我们也就得到了最长递增子序列的长度。从上述方法可知,对于每一个元素,我们需要对L进行查找操作,由于L有序,所以这个操作为logn,于是总的复杂度为O(nlogn)。优于开始O(n2)的算法。这里给出我的一个实现:(算法并没有返回具体的序列,只是返回长度)
template<typename
T>
int
LMS (const T* data,int
size)
...{
if (size<=0)
return0;
T* S=new
T[size];
int S_Count=1;
S[0]= data[0];
for (int i=1;
i< size; i++)
...{
const T&
e = data[i];
int low=0,
high= S_Count-1;
while (low<=
high)
...{
int mid=
(low + high)/2;
if (S[mid]==
e)
break;
elseif
(S[mid]> e)
...{
high= mid-1;
}
else
...{
low= mid+1;
}
}
//well,
in this point
//high
is -1, indicating e is the smallest element.
//otherwise, high indicates index of the largest element that is smaller than e
if
(high == S_Count-1)
S[S_Count++]=
e;
else
S[high+1]=
e;
}
return
S_Count;
}
T>
int
LMS (const T* data,int
size)
...{
if (size<=0)
return0;
T* S=new
T[size];
int S_Count=1;
S[0]= data[0];
for (int i=1;
i< size; i++)
...{
const T&
e = data[i];
int low=0,
high= S_Count-1;
while (low<=
high)
...{
int mid=
(low + high)/2;
if (S[mid]==
e)
break;
elseif
(S[mid]> e)
...{
high= mid-1;
}
else
...{
low= mid+1;
}
}
//well,
in this point
//high
is -1, indicating e is the smallest element.
//otherwise, high indicates index of the largest element that is smaller than e
if
(high == S_Count-1)
S[S_Count++]=
e;
else
S[high+1]=
e;
}
return
S_Count;
}
初看这个方法有点费解(这个算法转载于http://blog.csdn.net/fflush/article/details/1503841)
这里我举一个例子说明这个算法
data数组为1 3 5 7 9 5 5 6
S数组的变化依次是
(1)->(1,3)->(1,3,5)->(1,3,5,7)->(1,3,5,7,9)->(1,3,5,5,9)->(1,3,5,5,5)->(1,3,5,5,5,6)
最后得到的是(1,3,5,5,5,6)此数组对应每一项元素是L1,L2,L3,L4,L5,L6
而最长递增序列为6(注意S数组没有存一个可行解)
POJ 2544这个题的代码如下
#include <cstdio> #define SIZE 1010 using namespace std; int main() { int i, j, n, top, temp; int s[SIZE]; scanf("%d",&n); top = 0; s[0]=-1; for (i = 0; i < n; i++){ scanf("%d",&temp); if (temp >s[top]) s[++top] = temp; else{ int low = 1, high = top; int mid; //查找第一个大于等于temp的,因为要找单调增。 如果要求找单调不减的,要找第一个大于temp的 while(low <= high) { mid = (low + high)>>1; if (temp>s[mid]) low = mid + 1; else high = mid - 1; } s[low] = temp; } } printf("%d\n",top); return 0; }
HDU 3998
//lower_bound() O(logn) 查找第一个不小于k的元素 upper_bound() O(logn) 查找第一个大于k的元素
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define INF 100000 #define MAXN 100000 int dp[MAXN],data[MAXN],mark[MAXN]; int main() { int N,i,j,s,num,maxlen; while(scanf("%d",&N)!=EOF) { for(i=0;i<N;i++) { scanf("%d",&data[i]); } memset(mark,0,sizeof(mark)); s=0; num=1; while(1) { memset(dp,1,sizeof(dp)); maxlen=-INF; for(i=0;i<N;i++) { if(mark[i])continue; j=lower_bound(dp,dp+N,data[i])-dp; // 如果是求最长单调不减序列,则此处换为upper_bound(); dp[j]=data[i]; if(j>maxlen) { maxlen=j; mark[i]=1; } } if(s<maxlen+1)s=maxlen+1; else if(s==maxlen+1)num++; else break; } printf("%d\n%d\n",s,num); } return 0; }
HDU 3998 这个题的第二问也可以最大流去做,可以看做是求最多不相交路径