找出 最长递增子序列 所有最长子序列

如输入3

3 5 4 6

输出 3

3 4 5

3 5 6

思路：最长子序列有几个通过n*log(n)算出来

再用dfs+路径记录输出所有的值

#include<stdio.h>
#include<string.h>
#include<stack>
#include<iostream>
using namespace std;
#define MAXN 109

int ok=0;
int n,a[MAXN],s[MAXN];//ÐòÁдæÔÚsÀï
int t;//×ÓÐòÁг¤

int lis()//µ¥µ÷²»½µ×ÓÐòÁÐnlognËã·¨ 
{
    int l,r,mid,len=1;
    a[1]=s[1];
    for(int i=2;i<=n;i++)
    {
        l=1,r=len;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(a[mid]<s[i]) l=mid+1;//Ôö
            else r=mid-1;
        }
        a[l]=s[i];
        if(l>len) len++;
    }
    return len; 
}

int path[MAXN],r[MAXN];
void dfs(int step,int old,int add)
{
    if(step==t)
    {
        ok=1;
        stack<int>ss;
        
        ss.push(old);

        //printf("%d ",add);
        while(r[old]!=-1)
        {
            //printf("%d ",r[add]);
            ss.push(r[old]);
            old=r[old];
        }
        
        while(!ss.empty())
        {
            printf("%d ",s[ss.top()]);
            ss.pop();
        }

    //    memset(r,-1,sizeof(r));
        printf("\n");
        return ;
    }

    if(add>n) return ;


    dfs(step,old,add+1);
    
    if(s[add]>s[old])
    {
        r[add]=old;
        dfs(step+1,add,add+1);
    }
}

int main() 
{
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        for(i=1;i<=n;i++)
            scanf("%d",&s[i]);

        t=lis();
        printf("%d\n",t);

        
        for(i=1;i<=n+1-t;i++)
        {
            memset(r,-1,sizeof(r));

            ok=0;
            dfs(1,i,i+1);
        //    if(ok==0)
        //        break;
        }

    }
    return 0;
}