首页 > 代码库 > 最长单调递增子序列-LIS问题

最长单调递增子序列-LIS问题

http://zju.acmclub.com/index.php?app=problem_title&id=1&problem_id=1911

最长单减子序列、最长单增子序列、相继元素之间满足某种条件(例如绝对值之差不超过d)的最长子序列等,都是一个类型的动态规划。

下面给出一个n平方级别的基本算法。

思路:定义dp[i]代表A[i:n]中,以A[i]为开头的最长单增序列的长度。

从A[i-1]开始,最长单调递增序列应该按下列方法求出: 在A[i],A[i+1],A[i+2],…,A[n]中,找出一个比A[i-1]大的且最长的单增序列,

将A[i-1]接在该序列前面,即形成一个新的最长单增序列。

对于位置i-1,寻找A[i:n]中满足A[i-1]<A[j]的位置j,并取最大的dp[j],则dp[i-1]=dp[j]+1。

如果找不到这样的位置j,则以当前A[i-1]为开头的最长单增序列只包含它自己,更新dp[i-1]=1即可。

1.如果只要求输出最大长度,则遍历时记录dp[i]的最大值即可。

2.如果要求输出最长子序列,则遍历时使用一个数组记录相继位置,最后按序输出即可。

ps:本题可以改进成一个O(nlogn)的解法,思路是改进查找的策略,不要按序查找,可以用堆来维护。

c代码:

#include<stdio.h>
#define N 30
int main(){
    int A[N],dp[N];
    int i,j,n,k,L,MAX;
    while(scanf("%d",&n),n){
        for(k=0;k<n;k++){
            scanf("%d",&A[k]);
        }
        //printf("k=%d\n",k);
        dp[k-1]=1;//初始化最后一个
        MAX=1;
        for (i=k-2; i>=0; i--){
            L=0;//L记录最大长度
            for(j=i+1; j<=k-1; j++){
                if(A[i]>=A[j]&&dp[j]>L)L=dp[j];
            }
            if (L>0)dp[i]=L+1;
            else dp[i]=1;
            if(dp[i]>MAX)MAX=dp[i];
        }
        printf("%d\n",MAX);
    }
    return 0;
}


最长单调递增子序列-LIS问题