Pagini recente » Monitorul de evaluare | Diferente pentru warm-up-2019/solutii/shoturi intre reviziile 99 si 95 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2269884)
#include <fstream>
using namespace std;
ifstream fi("scmax.in");
ofstream fo("scmax.out");
int n;
int a[100001];
int dp[100001],ml;
int poz;
int main()
{
fi>>n;
for(int i=1; i<=n; i++)
fi>>a[i];
dp[n]=1;
for(int i=n-1; i>=1; i--)
{
ml = 0;
for(int j=i+1; j<=n; j++)
if(a[j]>a[i] and dp[j] > ml)
{
ml=dp[j];
}
dp[i]=ml+1;
}
int ma=0;
for(int i=1;i<=n;i++)
if(dp[i]>ma)
{
ma=dp[i];
poz=i;
}
int k=ma;
fo<<k << '\n';
fo<<a[poz]<<' ';
k--;
while(k)
{
for(int i=poz;i<=n;i++)
{
if(dp[i]==dp[poz]-1 and a[poz]<a[i])
{
k--;
poz=i;
fo<<a[i]<<" ";
}
}
}
return 0;
}
//maximul lungimilor subsirurilor crescatoare care incep dupa pozitia "i" cu un element >= a[i]