backtracking LIS

#include <bits/stdc++.h>
using namespace std;

int dp[2010], h[2010], bac[2010];

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> h[i];
    for(int i=0;i<n;i++) bac[i] = -1;

    // dynamic programming
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++)
            if(h[j] < h[i])
                if(dp[j] > dp[i]) dp[i] = dp[j], bac[i] = j;
        dp[i]++;
    }

    // find maximum value
    int maxx = -1e18, maxi = 0;
    for(int i=0;i<n;i++){
        if(dp[i] > maxx) maxx = dp[i], maxi = i;
    }
    cout << maxx << endl;

    // back tracking
    while(maxi >= 0){
        cout << h[maxi] << ' ';
        maxi = bac[maxi];
    }
    cout << endl;
}