Cod sursa(job #2763120)

Utilizator tigaieNedelcu Ioan-Andrei tigaie Data 11 iulie 2021 17:31:48
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#include <list>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i , n) for(int i = 0 ; i < (n) ; i++)
#define N 201
#define apare printf("apare");
#define endl "\n"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int , int> pii;
const int inf = 1e6;
const int nax = 50001;

void lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> sequence(n , 1);
    vector<int> ceva[n + 1];
    int ret = 1;
    int pos = 0; /// final pos
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j < i ; j++){
            if(nums[i] > nums[j] && sequence[i] < sequence[j] + 1){
                ceva[i].push_back(nums[j]);
                sequence[i] = sequence[j] + 1;
                ret = max(ret , sequence[i]);
                if(ceva[i].size() == ret - 1){
                    pos = i;
                }
            }
        }
    }
    cout << ret << endl;
    for(auto it : ceva[pos]){
        cout << it << " ";
    }
    cout << nums[pos];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("scmax.in" , "r" , stdin);
    freopen("scmax.out" , "w" , stdout);
    int n;
    cin >> n;
    vector<int> sequence;
    int buffer;
    FOR(i , n){
        cin >> buffer;
        sequence.push_back(buffer);
    }
    lengthOfLIS(sequence);
    return 0;
}