LIS

895. 最长上升子序列

#include<iostream>
using namespace std;
int v[1010];
int dp[1010];
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
        dp[i] = 1;
    }
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (v[j] < v[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int ret = 1;
    for (int i = 0; i < N; ++i) ret = max(ret, dp[i]);
    cout << ret << endl;
    return 0;
}

896. 最长上升子序列 II

O(n log k)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int>v(N);
    for (int i = 0; i < N; ++i) cin >> v[i];
    vector<int> lis;
    for (int i = 0; i < N; ++i) {
        auto it = lower_bound(lis.begin(), lis.end(), v[i]);
        if (it == lis.end()) {
            lis.push_back(v[i]);
        } else {
            // lis[it - lis.begin()] = v[i];
            *it = v[i];
        }
    }
    cout << lis.size() << endl;
    return 0;
}

LICS

O(n³) solution got TLE

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int f[N][N];
int a[N];
int b[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
    int ret = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = f[i-1][j];
            if (a[i] == b[j]) {
                int maxv = 1;
                for (int k = 0; k < j; ++k) {
                    if (b[k] < b[j]) {
                       maxv = max(maxv, f[i-1][k] + 1); 
                    }
                }
                f[i][j] = max(f[i][j], maxv);
                ret = max(ret, f[i][j]);
            }
        }
    }
    printf("%d\n", ret);
    return 0;
}

Improved O(n²)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int f[N][N];
int a[N];
int b[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) scanf("%d", &b[i]);
    for (int i = 1; i <= n; ++i) {
        int maxv = 1;
        for (int j = 1; j <= n; ++j) {
            f[i][j] = f[i-1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (b[j] < a[i]) maxv = max(maxv, f[i-1][j] + 1);
           
        }
    }
    int ret = 0;
    for (int j = 1; j <= n; ++j) ret = max(ret, f[n][j]);
    printf("%d\n", ret);
    return 0;
}