Cod sursa(job #2870114)

Utilizator Seress26Seres Artur Seress26 Data 12 martie 2022 09:40:27
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#define NMAX 100001
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,v[NMAX];
void Citire()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
}
void Rezolvare()
{
    int maxi=0,fin,st;
    vector <int> dp(n+1);
    dp[1]=1;
    maxi=dp[1];
    st=1;
    for(int i=2;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<=i-1;j++)
        {
            if(v[j]<v[i]&&dp[j]>=dp[i])
            {
                st=j-1;
                dp[i]=dp[j]+1;
            }
        }
        if(dp[i]>maxi)
        {
            maxi=dp[i];
            fin=i;
        }
    }
    int t=1;
    g<<maxi<<'\n';
    for(int i=fin-1;i>=1;i--)
    {
        if(v[i]<v[fin]&&dp[i]==dp[fin]-t)
        {
            st=i;
            t++;
        }
        if(dp[st]==1)
            break;
    }
    t=0;
    for(int i=st;i<=fin;i++)
    {
        if(dp[i]==dp[st]+t)
        {
            g<<v[i]<<' ';
            t++;
        }
        if(i==fin)
            break;
    }
}
int main()
{
    Citire();
    Rezolvare();

    return 0;
}