Cod sursa(job #2561789)

Utilizator TomKodeColev Thomas-Daniel TomKode Data 29 februarie 2020 10:08:27
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main()
{
    int v[100010],dp[100010]={0},finall[100001],n,sol=0;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
        dp[1]=1;
    for(int i=2;i<=n;i++)
    {
if(v[i]>v[i-1])
    dp[i]=dp[i-1]+1;
else
{
    int maxx=0;
for(int j=i;j>=1;j--)
{
if(v[i]>v[j])
{
        if(dp[j]>maxx)
            maxx=dp[j];
}
}
dp[i]=maxx+1;
}
if(dp[i]>sol)
    sol=dp[i];
    }
fout<<sol<<"\n";
int contor=n,ind=0;
while(sol)
{
    if(dp[contor]==sol)
    {
        finall[++ind]=v[contor];
        contor--;
        sol--;

    }
    else
    {
        contor--;
    }
    if(!contor)
        break;
}
for(;ind>=1;ind--)
    fout<<finall[ind]<<" ";
}