Cod sursa(job #2868851)

Utilizator meinkampfEmanuel Pinzariu meinkampf Data 11 martie 2022 11:04:46
Problema Subsir crescator maximal Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;

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

int cap[100002], ult[100002], a[100002], len[100002], n;
int nr_siruri, poz[100002];
/**

cap[i] - elementele din fiecare subsir nou creat

Recurenta:

dp[i] = 1 + max(dp[1]...dp[i - 1])

poz[i] - pozitia valorii care

*/

void Citire()
{
    int i, j, x, maxx;
    bool flag;
    fin >> n;
    for (i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
    cap[1] = a[1];
    nr_siruri = 1;
    poz[1] = 1;
    len[1]++;
    for (i = 2; i <= n; i++)
    {
        maxx = 0;
        flag = false;
        for (j = 1; j <= nr_siruri; j++)
        {
            if (cap[j] < a[i] && maxx < cap[j])
            {
                maxx = cap[j];
                poz[i] = j;
                flag = true;
            }
        }
        if (flag == false)
        {
            nr_siruri++;
            cap[nr_siruri] = a[i];
            len[nr_siruri]++;
            poz[i] = nr_siruri;
        }
        else
        {
            cap[poz[i]]++;
            len[poz[i]]++;
            cap[poz[i]] = a[i];
        }
    }
    maxx = 0;
    for (i = 1; i <= nr_siruri; i++)
    {
        if (maxx < len[i])
        {
            maxx = len[i];
            x = i;
        }
    }
    fout << maxx << '\n';
    for (i = 1; i <= n; i++)
    {
        if (poz[i] == x)
            fout << a[i] << ' ';
    }
}

int main()
{
    Citire();
    fin.close();
    fout.close();
    return 0;
}