Cod sursa(job #2855935)

Utilizator Seress26Seres Artur Seress26 Data 23 februarie 2022 10:44:30
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 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;
        }
    }

    /// daca v[i]==v[i-1] nu intra in for

    int max=0,id;
    for (int i=1;i<=n;i++)
        if (max<dp[i])
            id=i;
    fout<<dp[id]<<'\n';
    for (int i=v[id].second;i<=id;i++)
        if (v[i]!=v[i-1])
           fout<<v[i].first<<" ";
    return 0;
}