CP003201.LIS最长上升子序列
原题链接：657.LIS最长上升子序列
2023-12-10 18:15:03
发布于：江苏
99阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int f[N], n, a[N], ans=1;
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",a+i);
}
//状态转移
//以a[i]结尾的数字的LIS长度
for(int i=1; i<=n; i++) {
f[i]=1;
//遍历前i-1个数，看接在那个数后面最大
for(int j=1; j<=i-1; j++) {
if(a[i]>a[j]) {
f[i]=max(f[j]+1,f[i]);
}
}
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
全部评论 6
+--------------------------------------------------+ |██████████████████████████████████████████████| |██████████████ 文 保 碑 ██████████████████| |██████████████████████████████████████████████| |████████ 复仇者_x 遗址（上古时期） ███████████| |██████████████████████████████████████████████| |███████████ ACGO民间文物保护协会立 ███████████| |██████████████ 2026 年 9 月 5 日 ████████████| |██████████████████████████████████████████████| |██████████████████████████不会c++的c++█████████| |██████████████████████████████████████████████| +--------------------------------------------------+6天前 来自 江苏
2
有帮助，赞一个