Cod sursa(job #2197277)

Utilizator problem_destroyer69Daniel Hangan problem_destroyer69 Data 21 aprilie 2018 16:55:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 100005
#define pi pair<int,int>
#define pl pair<ll,ll>
//#define fin cin
//#define fout cout
int n,var,poz;
int a[MAXN],maxx[MAXN],prec[MAXN];

int main() {
    ifstream fin("scmax.in");
    ofstream fout("scmax.out");
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    maxx[n] = 1, poz = n;
    for (int i = n-1; i > 0; i--){
    maxx[i] = 1;
    for (int j = i+1; j <= n; j++)
    if (a[j] > a[i] && maxx[j] + 1 > maxx[i]){
        maxx[i] = maxx[j] + 1;
        prec[i] = j;
        if (maxx[i] > var){
            var = maxx[i];
            poz = i;
        }
    }
    }
    fout << var << "\n";
    while (poz){
        fout << a[poz] << ' ';
        poz = prec[poz];
    }
}