Pagini recente » Cod sursa (job #769071) | Istoria paginii runda/oni_mixt1/clasament | Cod sursa (job #760081) | Istoria paginii runda/simulare-cartita-46 | Cod sursa (job #979072)
Cod sursa(job #979072)
/// Craciun Catalin
/// Sir crescator de lungime maxima
/// www.infoarena.ro/problema/scmax
/// Programare dinamica
#include <fstream>
#include <iostream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int main(){
long n;
long long A[100001];
long L[100001]; /// Lungimea sirului crescator incepand cu pozitia i
long Poz[100001]; /// Urmatorul element din sirul crescator
/// Citire
f>>n;
for (long i=1;i<=n;i++)
f>>A[i];
f.close();
L[n]=1;
Poz[n]=-1;
for (long i=n-1;i>=1;i--){
L[i]=1;
Poz[i]=-1;
for (long j=i+1;j<=n;j++){
if (A[i]<=A[j] && L[i]<1+L[j]){
L[i]=1+L[j];
Poz[i]=j;
}
}
}
long max=L[1];
long pozMax=1;
for (long i=2;i<=n;i++)
if (max<L[i]){
max=L[i];
pozMax=i;
}
/// Afisare
g<<max<<"\n";
for (long i=pozMax;i!=-1;i=Poz[i])
g<<A[i]<<" ";
g.close();
return 0;
}