Cod sursa(job #1524810)

Utilizator kassay_akosKassay Akos kassay_akos Data 14 noiembrie 2015 14:20:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
using namespace std;

struct trii {
    int val,best,pre ;
};

trii v[100001];
int n ;

void Afisare(int ind);
int main()
{
    freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for(int i = 0; i<n; i++) {
        scanf("%d",&v[i].val);
        v[i].best = v[i].pre = -1;
	}
    v[0].best = 1;

    int maxim = 1, maxIndex =  0;
    int best, index ;
    for ( int i = 1;i < n; i++ ) {
        best = 0; index = -1;
        for (int j = i-1; j >= 0 ; j--) {
            if (v[j].val < v[i].val && v[j].best > best) {
                best = v[j].best;
                index = j;
            }
        }
        v[i].best = best + 1;
        v[i].pre = index;
        if (v[i].best > maxim) {
            maxIndex = i;
            maxim = v[i].best;
        }
    }
    int i = maxIndex , k = 1;
    while (v[i].pre != -1 ) {
        i = v[i].pre ;
        k++;
    }
    printf("%d \n",k);
    Afisare(maxIndex);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

void Afisare(int ind) {
    if (v[ind].pre == -1) {
        printf("%d ",v[ind].val);
        return;
    }
    Afisare(v[ind].pre);
    printf("%d ",v[ind].val);
}