Pagini recente » Cod sursa (job #2503573) | Cod sursa (job #1392759) | Cod sursa (job #2198123) | Cod sursa (job #2836873) | Cod sursa (job #1241267)
//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;
}