Cod sursa(job #1927052)

Utilizator RaTonAndrei Raton RaTon Data 14 martie 2017 21:39:44
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int V[100001], A[100001], D[100001];
int main()
{
    int n, i, j, mx, k;
    f >> n;
    for(i = 1; i <= n; i++)
        f >> V[i];
    A[n] = 1;
    for(i = n - 1; i >= 1; i--)
        for(j = i + 1; j <= n; j++)
            if( V[i] < V[j] && A[i] < A[j] + 1 ){
                A[i] = A[j] + 1;
                D[i] = j;
            }
    mx = A[1];
    k = 1;
    for(i = 1; i < n; i++)
        if(A[i] > mx){
            mx = A[i];
            k = i;
        }
    g << mx << '\n';
    g << V[k] << " ";
    while(D[k] != 0){
        k = D[k];
        g << V[k] << " ";
    }
    return 0;
}