B3637 最长上升子序列
dp模板题
以样例 1 2 4 1 3 4作为说明
每个数都是自己的一个子序列，所以全部初始化为1
从 1 - n 开始循环，定下来当前要计算的数 i
再从 1 - i 开始循环，判断 i 的最长上升子序列，定为 j
如果 i 比 j要大，则说明是上升的，此时的长度为 i 的长度与 j 的长度+1的最大值
也就得到了本题的核心
if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
最后遍历dp数组，得到最长上升子序列
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl "\n"
typedef pair<int, int> PII;
const int N = 5010;
int n;
int a[N];
int dp[N];
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], dp[i] = 1 ;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
signed main()
{
ios;
int T = 1;
//cin >> T;
while(T--)
{
solve();
}
return 0;
}