Mai intai trebuie sa te autentifici.
Cod sursa(job #305416)
| Utilizator | Data | 17 aprilie 2009 10:20:22 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 20 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.72 kb |
#include <fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int n, w[100001], t[100001], tt[100001];
long long v[100001];
void read()
{ f >> n;
for (int i=1; i<=n; i++)
f >> v[i];
}
void program()
{ for (int i=1; i<=n; i++)
for (int j=1; j<i; j++)
if (v[i]>v[j]) { w[i]=w[j]+1; t[i]=j; }
int max=0;
int h;
for (int k=1; k<=n; k++)
if (w[k]>max) { max=w[k]; h=k; }
g << max+1 << "\n";
int o=1;
while (h!=0)
{ tt[o++]=v[h];
h=t[h];
}
for (int m=o-1; m>=1; m--)
g << tt[m] << " ";
}
int main()
{ read();
program();
return 0;
}
