//LIS 最长上升子序列 o(n^2)
/*
arr[k]>arr[i]&&dp[k]<dp[i]+1
1 3 4 2 5
2 2 2 2
3 2 3
2 4
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=1000+10;
int arr[maxn],dp[maxn]; //dp[] 用来储存最优解
int main()
{
int n;
while(~scanf("%d",&n))
{
int ans=0;
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=0;i<n;i++)
{
for(int k=i+1;k<n;k++)
{
if(arr[k]>arr[i]&&dp[k]<dp[i]+1)
dp[k]=dp[i]+1;
}
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
//o(nlogN)
/*
1 3 4 2 5
1 2 3 2 4
*/
#include <stdio.h>
#include <string.h>
const int maxn=100000+10;
int arr[maxn],dp[maxn]; //dp[i] 最长上升子序列个数为i的所有子串结尾的最小值
int Search(int se_num,int right)
{
int middle,left=1;
while(left<=right)
{
middle=(left+right)/2;
if(dp[middle]<se_num)
left=middle+1;
else
right=middle-1;
}
return left;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int ini=1;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%d",&arr[i]);
dp[ini]=arr[1];
for(int i=2;i<=n;i++)
{
if(arr[i]>dp[ini])
dp[++ini]=arr[i];
else
{
int pos=Search(arr[i],ini);
dp[pos]=arr[i];
}
}
printf("%d\n",ini);
}
return 0;
}
//LCS o(n*m)
//用矩阵的方法将n,m作为行和列,有相同元素时为1不同时为0
//最长的公共子序列 每次记录时加上对角线上的值
/*
i==0,j==0 dp[i][j]=0;
i,j>0 a[i]==b[j] dp[i][j]=dp[i-1][j-1]+1;
i,j>0 a[i]!=b[j] dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=1000+10;
int a[maxn],b[maxn],dp[maxn][maxn]; //dp 记录最优解
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int k=1;k<=m;k++)
scanf("%d",&b[k]);
for(int i=1;i<=n;i++)
{
for(int k=1;k<=m;k++)
{
if(a[i]==b[k]) //字符串时改成a[i-1]==b[i-1]即可
dp[i][k]=dp[i-1][k-1]+1;
else
dp[i][k]=max(dp[i-1][k],dp[i][k-1]);
}
}
printf("%d\n",dp[n][m]);
}
return 0;
}
//LCIS o(n*m)
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=1000+10;
int a[maxn],b[maxn],dp[maxn]; //dp 记录以b[i]结尾的最优解
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int k=0;k<m;k++)
scanf("%d",&b[k]);
for(int i=0;i<n;i++)
{
int MAX=0;
for(int k=0;k<m;k++)
{
if(a[i]>b[k]&&MAX<dp[k]) //当a[i]==b[k]时 查找从1到k-1中的最优解
MAX=dp[k];
if(a[i]==b[k])
dp[k]=MAX+1;
}
}
int ans=0;
for(int i=0;i<m;i++)
if(ans<dp[i])
ans=dp[i];
printf("%d\n",ans);
}
return 0;
}