Cod sursa(job #1350091)
Utilizator | Data | 20 februarie 2015 17:38:03 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.85 kb |
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
ofstream g("scmax.out");
int a[100001],b[100001],c[100001],maxim,i,j,n,t;
int main()
{
freopen("scmax.in","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=1;
}
for(i=n-1;i>=1;i--)
{
for(j=n;j>=i+1;j--)
{
if(a[i]<a[j])
{
if(b[j]+1>b[i])
{
b[i]=b[j]+1;
c[i]=j;
}
}
}
}
maxim=0;
for(i=1;i<=n;i++)
{
if(b[i]>maxim)
{
maxim=b[i];
t=i;
}
}
g<<maxim<<'\n';
g<<a[t]<<" ";
while(c[t]!=0)
{
g<<a[c[t]]<<" ";
t=c[t];
}
return 0;
}