Pagini recente » Cod sursa (job #1152511) | Cod sursa (job #2508928) | Cod sursa (job #2469931) | Cod sursa (job #82438) | Cod sursa (job #648517)
Cod sursa(job #648517)
#include<iostream>
#include<fstream>
using namespace std;
int n, v[100001],dp[100001],pre[100001],sir[100001];
int maxx,imax;
void citire()
{
ifstream fin ("scmax.in");
fin>>n;
for (int i=1;i<=n;i++)
fin>>v[i];
fin.close();
}
void scr()
{
//pre[1]=0;
dp[1]=1;
for (int i=2;i<=n;i++)
{
dp[i]=1;
//pre[i]=0;
for (int j=i-1;j>=1;j--)
if (v[i]>v[j])
{
dp[i]=dp[j]+1;
pre[i]=j;
if (dp[i]>maxx) {maxx=dp[i]; imax=i;}
break;
}
}
}
void reconst()
{
ofstream fout("scmax.out");
fout<<maxx<<'\n';
int i=imax;
int j=1;
while (i>0)
{
sir[j++]=v[i];
i=pre[i];
}
for (int i=maxx;i>=1;i--)
fout<<sir[i]<<' ';
fout.close();
}
int main ()
{
citire();
scr();
/*cout<<"\ni: ";
for (int i=1;i<=n;i++) cout<<v[i]<<' ';
cout<<"\ndp: ";
for (int i=1;i<=n;i++) cout<<dp[i]<<' ';
cout<<"\npre: ";
for (int i=1;i<=n;i++) cout<<pre[i]<<' ';*/
reconst();
}