Cod sursa(job #1109672)
| Utilizator | Data | 17 februarie 2014 14:31:36 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.72 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100001],l[100001],x[100001];
int main()
{
int n,i,mx,poz,j;
f>>n;
for(i=0;i<n;i++)
f>>v[i];
l[n-1]=1;
for(i=n-2;i>=0;i--)
{
mx=0;
poz=0;
for(j=i+1;j<n;j++)
if(mx<l[j] && v[i]<v[j])
mx=l[j],poz=j;
l[i]=mx+1;
x[i]=poz;
}
mx=0;
poz=0;
for(i=0;i<n;i++)
{
if(mx<l[i])
mx=l[i],poz=i;
}
i=mx;
g<<mx<<"\n";
while(i!=0)
{
g<<v[poz]<<" ";
poz=x[poz];
i--;
}
return 0;
}
