Cod sursa(job #2856587)

Utilizator vladIordaIordachescu Vlad vladIorda Data 24 februarie 2022 09:13:46
Problema Subsir crescator maximal Scor 20
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;

/// pb de subsecventa sir maxim cu DP

ifstream fin("scmax.in");ofstream fout("scmax.out");

int main()
{
    int n;
    fin>>n;
    pair <int, int> v[n+1]; /// 1-val nr; 2-prefix (de unde incepe subsecventa)
    int dp[n+1];
    fin>>v[1].first;
    dp[1]=1;v[1].second=1;
    for (int i=2;i<=n;i++)
    {
        fin>>v[i].first;
        if (v[i-1].first<=v[i].first)
        {
            if (v[i-1].first<v[i].first)
                dp[i]=dp[i-1]+1;
            else
                dp[i]=dp[i-1];
            v[i].second=v[i-1].second;
        }
        else
        {
            dp[i]=1;
            v[i].second=i;
        }
    }
    int max=0,id;
    for (int i=1;i<=n;i++)
        if (max<dp[i])
        {
            id=i;
            max=dp[i];
        }
    fout<<max<<'\n';
    for (int i=v[id].second;i<=id;i++)
        if (v[i]!=v[i-1])
            fout<<v[i].first<<" ";
    return 0;
}