Pagini recente » Cod sursa (job #1503416) | Cod sursa (job #731010) | Cod sursa (job #1503696) | Cod sursa (job #2675955) | Cod sursa (job #979067)
Cod sursa(job #979067)
/// 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]){
if (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])
L[i]=max, pozMax=i;
/// Afisare
g<<max<<"\n";
for (long i=pozMax;i!=-1;i=Poz[i])
g<<A[i]<<" ";
g.close();
return 0;
}