最长公共子序列
一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=1000+10;
char A[N],B[N];
int f[N][N],la,lb;
void yzmain()
{
cin>>A>>B;
la=strlen(A),lb=strlen(B);
for(int i=1;i<=la;i++)
{
for(int j=1;j<=lb;j++)
{
if(A[i-1]==B[j-1])
f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
printf("%d\n",f[la][lb]);//长度
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
最长上升子序列
一个序列中最长的单调递增的子序列。
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=1000+10;
int f[N],a[N],n,ans=-1;
void yzmain()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<=i;j++)
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
ans=max(ans,f[i]);
}
printf("%d\n",ans);//长度
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/8480187ef853/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
