最长公共子序列 的 算法思路 在这里点击进入 将 代码稍微改动一下 就可以 , 最长公共子序列 是两个 字符串求 公共子序列 , 可以将其中的 一个 改为 从 a 到 z 这样输入另一个 就得到了 单调递增最长子 序列 下面附上题目 和 代码

这个是 时间复杂度 为 N 也算是 最优时间复杂度

1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack>10 #include<string>11 #include<sstream>12 #include<map>13 #include<cctype>14 using namespace std;15 int t,c[30][10005];16 char a[30],b[10005];17 int main()18 {19scanf("%d",&t);20for(int i=0;i<=26;i++)21 a[i]='a'+i;22while(t--)23{24 scanf("%s",b);25 int lb=strlen(b);26 memset(c,0,sizeof(c));27 for(int i=1;i<=26;i++)28 {29 for(int j=1;j<=lb;j++)30 {31 if(a[i-1]==b[j-1])32 c[i][j]=c[i-1][j-1]+1;33 else34 c[i][j]=c[i][j-1]>c[i-1][j]?c[i][j-1]:c[i-1][j];35 }36 }37 printf("%d\n",c[26][lb]);38}39return 0;40 }

下面附上一个时间复杂度为 N^2 的普通算法 ( 这个也算是比较普通 , 比较通用的算法了 )

1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack>10 #include<string>11 #include<sstream>12 #include<map>13 #include<cctype>14 #include<limits.h>15 using namespace std;16 int main()17 {18int t,l,dp[10005];19char a[10005];20scanf("%d",&t);21while(t--)22{23 scanf("%s",a);24 l=strlen(a);25 for(int i=0;i<l;i++)26 {27 dp[i]=1;28 }29 for(int i=1;i<l;i++)30 for(int j=0;j<i;j++)31 {32 if(a[i]>a[j])33 dp[i]=max(dp[i],dp[j]+1);34 }35 int maxn=INT_MIN;36 for(int i=0;i<l;i++)37 maxn=maxn>dp[i]?maxn:dp[i];38 printf("%d\n",maxn);39}40return 0;41 }

还有一个 时间复杂度 为 N log N 的 二分法 算法

1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<iostream> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<set> 9 #include<stack>10 #include<string>11 #include<sstream>12 #include<map>13 #include<cctype>14 #include<limits.h>15 using namespace std;16 int main()17 {18int t,l;19char a[10005],dp[10005];20scanf("%d",&t);21while(t--)22{23 scanf("%s",a);24 l=strlen(a);25 int location,num=0;26 for(int i=0;i<l;i++)27 {28 location=lower_bound(dp,dp+num,a[i])-dp;29 dp[location]=a[i];30 num=location+1>num?location+1:num;31 }32 printf("%d\n",num);33}34return 0;35 }