Cod sursa(job #2042582)

Utilizator skeniaTirla Ovidiu skenia Data 18 octombrie 2017 20:28:07
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <fstream>

#define cin fin
#define cout fout

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int length;
pair<int, int> con[100005];
int lengthCon = 1;
int finalMax = 0, finalMaxPoz = 0;


int getAssosciat(int number, int poz) {
    int lengthMax = 0, pozMax = 0;
    for (int iter = lengthCon; iter > 0; --iter) {
        if (con[iter].first < number && lengthMax <= con[iter].second) {
            lengthMax = con[iter].second;
            pozMax = iter;
        }
    }
    if (lengthMax > finalMax) {
        finalMax = lengthMax;
        finalMaxPoz = poz;
    }
    return pozMax;

}

void reversePrint(int poz) {
    if (con[poz].second != 0 || poz > 0) {
        reversePrint(con[poz].second);
        cout << con[poz].first << ' ';
        return;
    }
}

int main() {
    fin >> length;
    int temp;
    fin >> temp;
    con[lengthCon].first = temp;
    con[lengthCon].second = 0;
    lengthCon++;
    for (int iter = 2; iter <= length; ++iter) {
        fin >> temp;
        con[lengthCon].first = temp;
        con[lengthCon].second = getAssosciat(temp,iter);
        lengthCon++;
    }
    cout << con[finalMaxPoz].second << '\n';
    reversePrint(finalMaxPoz);

//    for (int iter = 0; iter < lengthCon; ++iter)
//        cout << con[iter].first << ' ';
//    cout << '\n';
//    for (int iter = 0; iter < lengthCon; ++iter)
//        cout << con[iter].second << ' ';
//    cout << '\n';
//    for (int iter = finalMaxPoz; con[iter].second > 0 || iter >= 1; iter = con[iter].second) {
//        cout << con[iter].first << ' ';
//    }
    fin.close();
    fout.close();
    return 0;
}