Cod sursa(job #3375783)

Utilizator genius112Prodan Alexandra genius112 Data 13 noiembrie 2026 16:50:16
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <deque>
#include <climits>
#include <bitset>
//#include "kor.h"

using namespace std;

int v[100001], dp[100001], n, i, j, maxi, rez, poz;
stack <int> q;

int main()
{
    ifstream cin ("scmax.in");
    ofstream cout ("scmax.out");

    cin >> n;

    for ( i = 1; i <= n; i++ ) {
        cin >> v[i];
    }
    for ( i = 1; i <= n; i++ ) {
        maxi = 0;
        for ( j = 1; j < i; j++ ) {
            if ( v[j] < v[i] ) {
                maxi = max ( maxi, dp[j] );
            }
        }
        dp[i] = maxi+1;
        if ( dp[i] > rez ) {
            rez = dp[i];
            poz = i;
        }
    }

    cout << rez << '\n';

    maxi = dp[poz];
    rez = v[poz];

    q.push(v[poz]);

    for ( i = poz-1; i >= 1; i-- ) {
        if ( v[i] < rez && maxi == dp[i]+1 ) {
            maxi = dp[i];
            rez = v[i];
            q.push(v[i]);
        }
    }
    while ( !q.empty() ) {
        cout << q.top() << ' ';
        q.pop();
    }

    return 0;
}