Cod sursa(job #1241267)
Utilizator | Ghinea Mihail Emanuel Eman98 | Data | 13 octombrie 2014 09:17:55 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.85 kb |
//Problema,folosind programare dinamica
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int best[100005],a[100005], Max,sol=0,poz[100005],p,n;
int main()
{
cin>>n;
int i, j;
for(i=1;i<=n;i++)
cin>>a[i];
best[n]=1;
poz[n]=-1;
Max=1;
p=n;
for(i=n-1;i>=1;--i)
{
best[i]=1;
poz[i]=-1;
for(j=i+1;j<=n;++j)
{
if(a[i]<a[j]&&best[i]<best[j]+1)
{
best[i]=best[j]+1;
poz[i]=j;
if (best[i]>Max)
{
Max=best[i];
p=i;
}
}
}
}
cout<<Max<<"\n";
int q;
q=p;
while(q!=-1)
{
cout<<a[q]<<" ";
q=poz[q];
}
return 0;
}