Cod sursa(job #2369422)

Utilizator Andreea62389Andreea Tebrean Andreea62389 Data 5 martie 2019 23:09:36
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100001], w[100001], o[100001];
int main()
{
    int n, i, maxx, j=0, maxim=0, poz, a;
    fin >> n;
    for(i=1; i<=n; i++)
    {
        fin >> v[i];
        maxx=0;
        for(j=1; j<i; j++)
            if(v[j]<v[i] && w[j]>maxx)   maxx=w[j];
        w[i]=maxx+1;
        if(w[i]>maxim){maxim=w[i];   poz=i;}
    }
    fout << maxim << "\n";
    a=v[poz]; i=1; o[i]=v[poz]; poz--;   maxim--;
    while(maxim)
    {
         if(v[poz]<a && w[poz]==maxim)
         {
             maxim--;
             a=v[poz];
             i++;
             o[i]=v[poz];
         }
         poz--;
    }
    while(i)
    {
          fout << o[i] << " ";
          i--;
    }

    return 0;
}