Cod sursa(job #2870443)

Utilizator k2y201342asdfadfsafsd k2y20 Data 12 martie 2022 12:43:01
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long
ifstream in("scmax.in");
ofstream out("scmax.out");

const int N=1e5;
int v[N+5],dp[N+5],poz[N+5];

int main()
{
    int n; in>>n;
    for(int i=1;i<=n;i++) in>>v[i];

    dp[1]=1,poz[1]=1;

    int lungMAX=-1,pozMAX=0;
    for(int i=2;i<=n;i++) //dp[i] = 1 + max(dp[j] | v[i]>v[j], 0 < j < i)
    {
        int lung=0,pz=0;

        for(int j=1;j<i;j++)
            if(v[j]<v[i] && dp[j] > lung) lung=dp[j],pz=poz[j];

        dp[i]=1+lung;
        if(!pz) poz[i]=i;
        else poz[i]=pz;

        if(dp[i] > lungMAX) lungMAX=dp[i],pozMAX=poz[i];
    }

    out<<lungMAX<<'\n';
    int anterior=v[pozMAX];
    for(int i=pozMAX+1,j=1;j<lungMAX;i++)
        if(v[i] > anterior)
    {
        out<<anterior<<' ';
        anterior=v[i];
        j++;
    }
    out<<anterior;
    return 0;
}