Cod sursa(job #3229059)
| Utilizator | Data | 13 mai 2024 16:35:05 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.7 kb |
#include <fstream>
using namespace std;
int v[100005],dp[100005],p[100005],save[100005];
int main()
{
ifstream cin("scmax.in");
ofstream cout("scmax.out");
int n,maxi=0,t;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
for(int j=i-1;j>0;j--)
{
if(v[j]<v[i])
if(dp[j]>dp[i])
{
dp[i]=dp[j];
p[i]=j;
}
}
dp[i]++;
if(dp[i]>maxi)
{
maxi=dp[i];
t=i;
}
}
cout<<maxi<<endl;
int k=0;
while(t!=0)
{
save[k]=v[t];
t=p[t];
k++;
}
for(int l=k-1;l>=0;l--)
{
cout<<save[l]<<' ';
}
return 0;
}
