Cod sursa(job #881076)

Utilizator raulmuresanRaul Muresan raulmuresan Data 17 februarie 2013 18:07:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>

using namespace std;

int i, j, n, LungMax, v[100005], lung[100005];

int main() {

    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);

    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        lung[i] = 1;
    }

    for (i = n - 1; i >= 1; i--) {
        for (j = i + 1; j <= n;j++) {
            //printf("%d %d\n",i,j);
        if (v[i] < v[j] && lung[i] < lung[j] + 1)
                lung[i] = lung[j] + 1;
        }
        if (LungMax < lung[i])
            LungMax = lung[i];
    }
    printf("%d\n",LungMax);


    i=1;
    while (LungMax) {
        if (lung[i] == LungMax) {
            --LungMax;
            printf("%d ",v[i]);
        }
        ++i;
    }





}