Cod sursa(job #1612093)
Utilizator | Nitu Anca Gabriela Anca-Gabriela | Data | 24 februarie 2016 18:20:32 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.57 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
long v[5000],w[5000],i,j,n,k;
int main()
{
f>>n;
for(i=1;i<=n;i++) f>>v[i];
w[n]=0;
for(i=n-1;i>=1;i--)
{
w[i] = 0;
for (j = i + 1; j <=n; j++)
{
if (v[i] < v[j] && w[i] <= w[j]) w[i] = w[j] + 1;
}
}
// for(i=1;i<=n;i++) cout<<w[i]<<" ";
// cout<<endl;
k=w[1];
for(i=1;i<=n;i++) if(w[i]>k) k=w[i];
g<<k+1;
for(i=1;i<=n;i++) if(w[i]==k) {g<<v[i]<<" "; k--;}
return 0;
}