Cod sursa(job #1400711)

Utilizator danysilas23Silas Daniel danysilas23 Data 25 martie 2015 13:27:37
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <math.h>
#include <algorithm>
#include <fstream>
using namespace std;
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");

    int n, v[100003], sm[100003], aux[100003];

void citire()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>v[i];
}
void sol()
{
    sm[n] = 1;
    aux[0] = 2000000001;
    aux[1] = v[n];
    int i,l = 1,val;
    for(i = n - 1; i; i--)
  {
    int t=l;
    while(v[i] >= aux[t])
    t--;
    sm[i] = t+1;
    aux[ sm[i] ] = max(v[i],aux[sm[i]]);
    if(l < sm[i])
    l = sm[i];
  }
    val = 0;
    cout << l << '\n';
    for(i = 1; i <= n; i++)
    if(sm[i] == l && v[i] > val)
  {
    cout << v[i] << ' ';
    l--;
    val = v[i];
  }}
  int main()
{
    citire();
    sol();
    return 0;
}