Playing with sequences

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

#define ll long long
#define nl '\n'

void solve(){
    int n; cin >> n;
    vector<int> v(n);
    for(auto& i : v)
        cin >> i;

    vector<vector<int>> dp(n + 1, vector<int>(2, 1));

    // dp[i][0] -> longest sequence ending here with a bigger previous
    // dp[i][1] -> //       //        //   //   //     smaller //

    vector<vector<int>> prev(n + 1, vector<int>(2, -1));

    for(int i = 1; i <= n; i++){
        for(int j = i - 1; j >= 1; j--){
            if(v[j - 1] < v[i - 1] and dp[j][0] + 1 > dp[i][1]){
                dp[i][1] = dp[j][0] + 1;
                prev[i][1] = j;
            }

            if(v[j - 1] > v[i - 1] and dp[j][1] + 1 > dp[i][0]){
                dp[i][0] = dp[j][1] + 1;
                prev[i][0] = j;
            }
        }
    }

    int ans = 0;
    for(auto& i : dp){
        ans = max(ans, *max_element(i.begin(), i.end()));
    }

    int st = -1;
    bool dir;
    for(int i = n; i >= 0; i--){
        if(dp[i][0] == ans){
            st = i;
            dir = false;
            break;
        }
        if(dp[i][1] == ans){
            st = i;
            dir = true;
            break;
        }
    }


    stack<int> path;
    path.push(v[st - 1]);

    while(prev[st][dir] != -1){
        path.push(v[prev[st][dir] - 1]);
        st = prev[st][dir];
        dir = not dir;
    }

    cout << ans << nl;
    while(not path.empty()){
        cout << path.top() << ' ';
        path.pop();
    }
}

int main(){
//    freopen("collector.in", "r", stdin);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int t = 1;
//    cin >> t;
    while(t--){

        solve();
        if(t)
            cout << nl;
    }

    return 0;
}