Cod sursa(job #2477578)

Utilizator XXMihaiXX969Gherghinescu Mihai Andrei XXMihaiXX969 Data 20 octombrie 2019 18:43:49
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("scmax.in");
ofstream out("scmax.out");

long long v[100007];

int arr[100007];
int poz[100007];
void lungime(int n,int rez)
{
    int p;
    poz[n] = -1;
    for(int i = n-1;i >= 1;i--)
    {
     poz[i] = - 1;
    for(int j = i+1;j <= n;j++)
    if(v[i] < v[j] && arr[i] < arr[j] + 1 )
    {
    arr[i] = arr[j] + 1;
    poz[i] = j;
    if(arr[i] > rez)
        {rez = arr[i];
        p = i;
        }
    }
    }
    out << rez << "\n";
    while(p!=-1)
    {
        out << v[p] <<" ";
        p = poz[p];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    in.tie(0);
    int n;
    in >> n;
    for(int i = 1 ;i <= n;i++)
    {
      in >> v[i];
      arr[i] = 1;
    }
    int rez = 0;
    lungime(n,rez);
    return 0;
}