Cod sursa(job #2042611)

Utilizator skeniaTirla Ovidiu skenia Data 18 octombrie 2017 20:47:12
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>


using namespace std;

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

int length;
int con[3][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[0][iter] < number && lengthMax <= con[2][iter]) {
            lengthMax = con[2][iter];
            pozMax = iter;
        }
    }
    if (lengthMax > finalMax) {
        finalMax = lengthMax;
        finalMaxPoz = poz;
    }
    return pozMax;

}

void reversePrint(int poz) {
    if (con[1][poz]!= 0 || poz > 0) {
        reversePrint(con[1][poz]);
        fout << con[0][poz] << ' ';
        return;
    }
}

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

//    for (auto &line : con) {
//        for (int iter = 0; iter < lengthCon; ++iter) {
//            cout << line[iter] << ' ';
//        }
//        cout << '\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[1][iter] > 0 || iter >= 1; iter = con[1][iter]) {
//        cout << con[0][iter] << ' ';
//    }
    fin.close();
    fout.close();
    return 0;
}