企业官网建设流程全解析

题目描述

这是一个简单的动规板子题。

给出一个由 n(n≤5000) 个不超过 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序尽可能多取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 n，表示序列长度。

第二行有 n 个整数，表示这个序列。

输出格式

一个整数表示答案。

输入输出样例

in: 6 1 2 4 1 3 4 out: 4

说明/提示

分别取出 1、2、3、4 即可。

无广（叠甲）诚挚推荐NotOnlySuccess （B站Up主）

https://www.bilibili.com/video/BV1WJGnz5EQK/?spm_id_from=333.337.top_right_bar_window_history.content.click&vd_source=60655a98e076f0956ec8acbf8f14132d

代码如下（发明天才的真是个STL标准库）

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int>dp; for(auto x:a){ auto iter=lower_bound(dp.begin(),dp.end(),x); if(iter==dp.end())dp.push_back(x); else *iter=x; } cout<<dp.size()<<endl; return 0; }