描述

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

输入

第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入

3aaaababcabklmncdefg

样例输出

137

 

 1  #include <assert.h> 2 #include <error.h> 3 #include <unistd.h> 4 #include <sys/types.h> 5 #include <signal.h> 6 #include <pthread.h> 7 #include <stdio.h> 8 #include <unistd.h> 9 #include <stdlib.h>10 #include <pthread.h>11 #include <string.h>12 int dep[10000];13 int max(int a, int b){14     return (a>b)?a:b;15 }16 17 //aesc18 int cmp(const void*a, const void *b){19     return *((int *)a)>*((int *)b)?0:1;20 }21 22 int dp(char *buf, int len){23     int i,j;24     int tmp=0;25     int k;26     for (k = 0; k < 10000; ++k) {27         dep[k] = 1;28     }29     for (i = 0; i < len; ++i) {30         for (j = 0; j < i; ++j) {31             if (buf[i] > buf[j]) {32                 dep[i] = max(dep[j]+1, dep[i]);33             }34         }35     }36 37     qsort(dep, len, sizeof(int), cmp);38     tmp = dep[0];39 40     /*41     for (k = 0; k < len; ++k) {42         printf("%d ", dep[k]);43     }44     printf("\n");45 46     for (k = 0; k < 10000; ++k) {47         if(dep[k] > tmp){48             tmp = dep[k];49         }50     }*/51     return tmp;52 }53 54 int main(){55     int n;56     scanf("%d", &n);57     getchar();58     while (n--) {59         char buf[10000] = {0};60         scanf("%s", buf);61         getchar();62        int len = (int)strlen(buf);63        int max = dp(buf, len);64         printf("%d\n", max);65     }66     exit(EXIT_SUCCESS);67 }68         

View Code

 

单调递增最长子序列