Cod sursa(job #2164900)
| Utilizator | Data | 13 martie 2018 10:21:57 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.59 kb |
#include<bits/stdc++.h>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int N,v[100001],best[100001],poz[100001],Max,idx;
int main()
{
f>>N;
for(int i=1;i<=N;++i)f>>v[i],best[i]=1,poz[i]=-1;
for(int i=2;i<=N;++i){
for(int j=1;j<i;++j)
if(v[j]<v[i]&&best[j]+1>best[i]){
best[i]=best[j]+1,poz[i]=j;
}
if(best[i]>Max)Max=best[i],idx=i;
}
g<<Max<<'\n';
int k=idx;
idx=Max;
while(k!=-1)best[idx--]=v[k],k=poz[k];
for(int i=1;i<=Max;++i)g<<best[i]<<' ';
return 0;
}
