Cod sursa(job #2856596)

Utilizator vladIordaIordachescu Vlad vladIorda Data 24 februarie 2022 09:33:47
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 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].first==v[i-1].first)
        {
            n--;
            i--;
        }
        else
        {
            if (v[i-1].first<v[i].first)
            {
                dp[i]=dp[i-1]+1;
                v[i].second=v[i-1].second;
            }
            else
            {
                dp[i]=1;
                v[i].second=i;
            }
        }
    }
    int id=1;
    for (int i=1;i<=n;i++)
        if (dp[id]<dp[i])
            id=i;
    fout<<dp[id]<<'\n';
    for (int i=v[id].second;i<=id;i++)
        if (v[i].first!=v[i-1].first)
            fout<<v[i].first<<" ";
    return 0;
}