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;
}