#include <iostream>
#define N 8
using namespace std;
int main(){    
    int a[N]={1,-1,2,-3,4,-5,6,-7};
    int lis[N];
    int result[N];//结果
    for(int i=0;i<N;i++)
            result[i]=0;
    for(int i=0;i<N;i++)
    {
        lis[i]=1;
        for (int j=0;j<i; j++)
        {
            if( a[i]> a[j] && lis[i] < lis[j]+1){
                lis[i]=lis[j]+1;
            }
        }        
    }
    int m=0;
    for(int i=0;i<N;i++){
        if(m<lis[i])
            m=lis[i];
    }
    cout<<"最长递增子序列为："<<m<<endl;
    //用回溯法输出最长递增子序列
    int b=m;
    int sum=0;
    for(int t=N;t>=0;t--){
        if (b > m)
            break;
        if(lis[t] == b){
            result[t]=1;
            b=b-1;
            if(b  ==  0){
                char p[30];
                sprintf(p,"第%d个最长递增子序列",++sum);
                cout<<p<<endl;
                //输出
                for(int g=0;g<N;g++){
                    if(result[g] == 1)
                         cout<<a[g]<<" ";
                }
                cout<<endl;
                //复原
                b=b+1;
                result[t]=0;
            }

        }
        if( t == 0){
            b=b+1;
            int r;
            //回溯
            for(r=0;result[r]!=1&&r<N;r++);
            if(r<N){
                t=r;
                result[t]=0;
            }
        }
    }    
    system("pause");
    return 0;
}

最长递增子序列为：4
第1个最长递增子序列
-1 2 4 6
第2个最长递增子序列
1 2 4 6