Cod sursa(job #1916565)

Utilizator EwaruCiorba Bogdan Ewaru Data 9 martie 2017 09:49:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
using namespace std;
void citire(int &n, int (&v)[100001])
{
    ifstream f("scmax.in");
    f>>n;
    for (int i=1;i<=n;i++)
        f>>v[i];
    f.close();
}
void solve(int &n, int (&v)[100001])
{
    int lung[100001],maxi=0,i,j,poz;
    lung[n-1]=1;
    for (i=n;i>=0;i--)
    {       maxi=0;
            for(j=i+1;j<=n;j++)
                if (v[i]<v[j])
                    if (maxi<lung[j])
                        maxi=lung[j];
            lung[i]=maxi+1;
    }

    maxi=0;
    poz=0;
    for (i=1;i<=n;i++)
        if (maxi<lung[i])
            maxi=lung[i],poz=i;
    ofstream g("scmax.out");
    g<<maxi<<'\n';
    g<<v[poz]<<' ';
    for (i=poz+1;i<=n;i++)
        if (lung[i]==maxi-1 && v[i]>v[poz])
        {
            g<<v[i]<<' ';
            poz=i;
            maxi--;
        }
    g.close();

}
int main()

{
    int n,v[100001];
    citire(n, v);
    solve(n, v);
    return 0;
}