Cod sursa(job #2527344)

Utilizator davidcotigacotiga david davidcotiga Data 20 ianuarie 2020 09:39:06
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <stdlib.h>

using namespace std;

ifstream cin ("scmax.in");
ofstream cout("scmax.out");

const int MAX = 100005;
int v[MAX], lung[MAX], poz[MAX];

int main(){
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i){
        cin >> v[i];
        int max = 0, poz_temp = 0;
        for (int j = i; j > 0; --j){
            if (v[i] > v[j] && lung[j] > max){
                max = lung[j];
                poz_temp = j;
            }

            if (max != 0)
                poz[i] = poz_temp;
        }
        lung[i] = max + 1;
    }

    /*for (int i = 1; i <= n; ++i)
        cout << lung[i] << " ";
    cout << "\n";

    for (int i = 1; i <= n; ++i)
        cout << poz[i] << " ";*/

    int max = 0, poz_temp = -1;
    for (int i = 1; i <= n; ++i)
        if (lung[i] > max){
            max = lung[i];
            poz_temp = i;
        }

    cout << max << "\n";

    int rez[MAX], k = 0;
    while (poz_temp != 0){
        rez[k++] = v[poz_temp];
        poz_temp = poz[poz_temp];
    }
    for (int i = k - 1; i >= 0; --i)
        cout << rez[i] << " ";

    return 0;
}