Cod sursa(job #991729)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 31 august 2013 12:48:20
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
using namespace std;
int dp[2][100001], v[100001], a[1001], n;
void citire(){
    freopen("scmax.in", "r", stdin);
    scanf("%d ",&n);
    for(int i = 1; i <= n; ++i)
        scanf("%d ",&v[i]);
}
void solve(){
    int i=0, j=0, maxi=1, k=0, poz=0, maxi1=0;
    dp[1][1]=1;
    dp[2][1]=0;
    for(i = 2; i <= n; ++i){
        for(j = i - 1; j > 0; --j)
            if(v[j] < v[i] && maxi1 < dp[1][j]){
                dp[2][i] = j;
                maxi1 = dp[1][j];
            }
        dp[1][i] = maxi1 + 1;
        if(dp[1][i] > maxi){
            maxi = dp[1][i];
            poz = i;
        }
        maxi1=0;
    }
    printf("%d\n",maxi);
    while(dp[2][poz]){
        a[++k] = v[poz];
        poz = dp[2][poz];
    }
    a[++k]=v[poz];
    for(j = k; j > 0; --j)
        printf("%d ",a[j]);
}
int main(){
    freopen("scmax.out", "w", stdout);
    citire();
    solve();
}