Cod sursa(job #1643648)

Utilizator CidanielCraciun Ioan Daniel Cidaniel Data 9 martie 2016 19:39:31
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
long i, ii, j, n, v[100005], s[100005], k[100005],  M, Max, Mmax;
int main()
{
    f>>n;
    for (i=0; i<n; i++)
        {
            f>>v[i];
            s[i]=1;
        }
    if (n==1)
        {
            g<<1<<'\n'<<v[0];
            f.close();
            g.close();
            return 0;
        }
    M=1;
    for (i=1; i<n; i++)
        {
            Max=0;
            for (j=0; j<i; j++)
                {
                    if (v[j]<v[i])
                        {
                            if (s[j]>Max)
                                {
                                    Max=s[j];
                                }
                        }
                }
            s[i]+=Max;
            if (s[i]>M)
                {
                    M=s[i];
                    ii=i;
                }
        }
    g<<M<<'\n';
    Mmax=Max;
    k[Max]=v[ii];
    i=ii;
    ii--;
    while (Max>0)
        {
            if ((v[ii]<v[i])&&(s[ii]==s[i]-1))
                {
                    i=ii;
                    Max--;
                    k[Max]=v[ii];
                }
            ii--;
        }
    for (i=0; i<=Mmax; i++)
        {
            g<<k[i]<<' ';
        }
    f.close();
    g.close();
    return 0;
}