Cod sursa(job #2506150)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 7 decembrie 2019 16:57:10
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#define MAX 100005

using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n, a[MAX], b[MAX], l, pos[MAX];

int main()
{
    int i, j;
    fin >> n;

    for (i = 1; i <= n; i++)
        fin >> a[i];

    for (i = 1; i <= n; i++) {
        b[i] = 1;
        pos[i] = 0;
        for (j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                if (b[i] < b[j]+1) {
                    b[i] = b[j]+1;
                    pos[i] = j;
                }
            }
        }
        if (b[i] > b[l])
            l = i;
    }

    fout << b[l] << "\n";
    int k = 1;
    while (a[l]) {
        b[k++] = a[l];
        l = pos[l];
    }
    for (i = k-1; i > 0 ; i--)
        fout << b[i] << " ";
    return 0;
}