Pagini recente » Cod sursa (job #1087628) | Cod sursa (job #2000493) | Cod sursa (job #15919) | Cod sursa (job #2063945) | Cod sursa (job #2163374)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100000],best[100000],poz[100000],n,M,p;
void citire()
{
f>>n;
for(int i=0;i<n;i++)
f>>v[i];
f.close();
}
void dinamic()
{
best[n-1]=1;
poz[n-1]=-1;
int i,j;
M=1;p=n-1;
for(i=n-2;i>=0;i--)
{
best[i]=1;
poz[i]=-1;
for(j=i+1;j<n;j++)
{
if(v[i]<v[j]&&best[i]<=best[j])
{
best[i]=best[j]+1;
poz[i]=j;
}
}
if(best[i]>M)
{M = best[i];p=i;}
}
}
void afisare()
{
int k=p;
g<<M<<"\n";
while(k!=-1)
{
g<<v[k]<<" ";
k=poz[k];
}
g.close();
}
int main()
{
int n;
citire();
dinamic();
afisare();
return 0;
}