Cod sursa(job #1112046)

Utilizator larisaaDanaila Larisa Andreea larisaa Data 19 februarie 2014 13:00:49
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> pd, a, lg;

ifstream f("scmax.in");
ofstream g("scmax1.out");

int main()
{
    int i,j,n,max,pozmax,lgmax;
    f>>n;
    pd.resize(n+1);
    a.resize(n+1);
    lg.resize(n+1);
    for (i=1; i<=n; i++)
        f>>a[i];
    for (i=n-1; i>=1; i--)
        {max=-1;
        for(j=i+1;j<=n;j++)
            if(lg[i]>max && a[i]<a[j])
                {
                max=lg[j];
                pozmax=j;
                }
        lg[i]=max+1;
        pd[i]=pozmax;
        }
lgmax=-1;
for(i=1;i<=n;i++)
    if(lg[i]>lgmax)
    {
        lgmax=lg[i];
        pozmax=i;
    }
i=pozmax;
g<<(lgmax+1)<<'\n';
while(i!=0)
{
    g<<a[i]<<' ';
    i=pd[i];
}
return 0;
}