Cod sursa(job #2613453)
Utilizator | Nae Teodora Ioana teodora019 | Data | 9 mai 2020 19:54:45 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.76 kb |
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int a[100001], d[100001], re[100001];
int main() {
int n, i, j, maxx, p;
cin>>n;
for(i=1; i<=n; i++)
cin>>a[i];
d[n]=1;
re[n]=-1;
maxx=1;
p=n;
for (i=n-1; i>0; i--)
{d[i]=1;
re[i]=-1;
for(j=i+1; j<=n; j++)
{
if(d[j]+1>d[i] && a[j] > a[i])
{d[i]=d[j]+1;
re[i]=j;
}
if (d[i]>maxx) {
maxx=d[i];
p=i;
}
}
}
cout<<maxx<< '\n';
i=p;
do
{
cout<<a[i]<<' ';
i=re[i];
}
while(i!=-1);
return 0;
}