首页 > > 程序设计 > C/C++ >

递增序列

2018-06-17 21:56:05来源：未知阅读 ()

描述
    求一个字符串的最长递增子序列的长度
    如：dabdbf最长递增子序列就是abdf，长度为4

输入
    第一行一个整数0<n<20,表示有n个字符串要处理
    随后的n行，每行有一个字符串，该字符串的长度不会超过10000
输出
    输出字符串的最长递增子序列的长度

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int dizeng(char a[])
{
        int x[10000] = {0};//全局变量
        x[0] = 1;
        int i, j;
        int n = strlen(a);
        for(i = 1; i <= n - 1; i++)//寻找数组中长度最长的递增子数列
        {
                x[i] = 1;//x[i]的最小值为1；
                for(j = 0; j < i; j++)//循环i 次
                {
                       if(a[j] < a[i] && x[j] > x[i]-1)
                              x[i] = x[j] + 1;//更新x[i]的值。
                }
        }
        int max = 0;
        for(i = 0; i < n; i++)
        {
                if(max < x[i])
                        max = x[i];
        }
        return max;//子数列的长度
}
int main ()
{
        int n;
        cin>>n;
        int k = 0;
        int m[n] = {0};
        char a[10000];
        while(k < n)
        {
                cin>>a;
                m[k] = dizeng(a);
                k++;
        }
        for(int i = 0; i < n; i++)
                cout<<m[i]<<endl;
        return 0;
}