Cod sursa(job #1068663)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 28 decembrie 2013 16:28:41
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//
//  main.cpp
//  scmax
//
//  Created by Catalina Brinza on 10/19/13.
//  Copyright (c) 2013 Catalina Brinza. All rights reserved.
//

#include <set>
#include <fstream>
using namespace std;

#include <iostream>
#include <fstream>
using namespace std;
int main()
{int n,i,j,k=0,l=0, v[100001],s[100001],pred[100001];
    set <int> vec;
    ifstream f("scmax.in");
    ofstream g("scmax.out");
    f>>n;
    for (i=0;i<n;i++)
        f>>v[i];
    s[0]=1;
    for (i=0;i<n;i++)
        f>>v[i];
    s[0]=1;
    for (i=1;i<n;i++)
    {s[i]=1;
        pred[i]=-1;
        k=0;
        for ( j = 0; j < i; ++j )
            if ( v[j] < v[i] && s[j] + 1 > s[i] ) {
                s[i] = s[j] + 1;
                pred[i] = j;
            }
        if (s[i]>l)
        {k=i;
            l=s[i];
        }
    }
    g<<l<<endl;
    i=k;
    vec.insert(k);
    while (pred[i]!=-1)
    {
        vec.insert(pred[i]);
        i=pred[i];
    }
    for (set<int>::iterator it =vec.begin();it!=vec.end();++it)
    {
        g<<v[*it]<<' ';
    }
    g.close();
    return 0;
}