Cod sursa(job #2750464)

Utilizator michael_blazemihai mihai michael_blaze Data 11 mai 2021 15:16:04
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <stack>
#define MAX 100005
#define INF 2147483647

using namespace std;

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

int n;
int arr[MAX];
int SCM[MAX];
int answer;

int max(int x, int y)
{
    return x > y ? x : y;
}


void read()
{
    fin >> n;
    for (int i = 0; i < n; ++ i)
        fin >> arr[i];
}

void solve()
{
    SCM[0] = 1;

    for (int i = 1; i < n; ++ i)
    {
        int maxim = 1;

        for (int j = 0; j < i; ++ j)
            if (arr[j] < arr[i])
                maxim = max(SCM[j] + 1, maxim);

        SCM[i] = maxim;
    }

    answer = 1;
    for (int i = 0; i < n; ++ i)
        answer = max(answer, SCM[i]);
}

void print()
{
    int lastAnswer = INF;
    stack<int> result;

    fout << answer << endl;

    for (int i = n - 1; i >= 0; -- i)
    {
        if (answer == SCM[i] && arr[i] < lastAnswer)
        {
            result.push(arr[i]);
            answer -= 1;
            lastAnswer = arr[i];
        }
    }

    while (!result.empty())
    {
        fout << result.top() << ' ';
        result.pop();
    }
}

int main() {
    read();
    solve();
    print();
    return 0;
}