Cod sursa(job #1781835)

Utilizator andreinmAndrei andreinm Data 17 octombrie 2016 15:14:21
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;

int i, N, _max = -1, pos_max;
int arr[100001], D[100001];


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

void print(int D[], int n) {
    int k = 0;
    int ans[100001];

    out << _max << '\n';

    ans[++k] = arr[pos_max];
    for (int i = pos_max - 1; i >= 1; i--) {
        if (D[i] == D[i+1] - 1 && arr[i] < arr[i+1])
            ans[++k] = arr[i];
    }
    reverse(ans + 1, ans + k + 1);
    for (int i = 1; i <= k; ++i)
        out << ans[i] << ' ';
}

void solve(int arr[], int n) {
    int i, j;
    for (i = 1; i <= n; i++)
        D[i] = 1;

    for (i = 2; i <= n; i++ )
        for (j = 1; j < i; j++)
            if (arr[i] > arr[j] && D[i] < D[j] + 1)
                D[i] = D[j] + 1;

    for (i = 1; i <= n; i++)
        if (_max < D[i])
            _max = D[i], pos_max = i;

    print(D, N);
}

int main()
{
    in >> N;
    for (i = 1; i <= N; ++i)
        in >> arr[i];

    solve(arr, N);

    return 0;
}