Cod sursa(job #1504039)

Utilizator Andrei66Andrei Rusu Andrei66 Data 17 octombrie 2015 11:34:27
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>
#define VM 100005

using namespace std;

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

int n, v[VM], dp[VM], t[VM];

void write(int p){
    if(p != -1){
        write(t[p]);
        g<<v[p]<<" ";
    }
}

int main()
{
    f>>n;
    for(int i=1; i<=n; ++i){
        f>>v[i];
        dp[i] = 1;
        t[i] = -1;
    }

    for(int i=1; i<=n; ++i)
        for(int j=1; j<i; ++j)
            if(v[j] < v[i] && dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1;
                t[i] = j;
            }
    int sol = 1, poz = 1;
    for(int i=1; i<=n; ++i)
        if(sol < dp[i]) {
            sol = dp[i];
            poz = i;
        }
    g<<sol<<'\n';
    write(poz);


    return 0;
}