Pagini recente » Cod sursa (job #887245) | Cod sursa (job #2506523) | Cod sursa (job #1320015) | Cod sursa (job #3237470) | Cod sursa (job #951316)
Cod sursa(job #951316)
#include <fstream>
using namespace std;
#define nmax 100002
int n,i,a[nmax],best[nmax],j,maxi,maxim,poz,k;
ifstream f("scmax.in");
ofstream g("scmax.out");
void c()
{
f>>n;
for (i=1;i<=n;i++)
f>>a[i];
}
void dinamica()
{
best[n]=1;
maxim=0;
for (i=n-1;i>=1;i--){
maxi=0;
for (j=i+1;j<=n;j++)
if (a[i]<a[j] && maxi<best[j]) maxi=best[j];
best[i]=maxi+1;
if (best[i]>maxim) maxim=best[i],poz=i;
}
}
void reconst()
{
for (k=poz;k<=n;k++)
if (a[poz]<=a[k] && best[k]==maxim) g<<a[k]<<' ',maxim--,poz=k;
}
int main()
{
c();
dinamica();
g<<maxim<<'\n';
reconst();
return 0;
}