Cod sursa(job #1542614)

Utilizator sing_exFMIGhita Tudor sing_ex Data 5 decembrie 2015 15:12:33
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <stack>

using namespace std;

int main()
{
    int n,i,j,maxpos = -1,h;
    stack<int> st;
    ifstream f("scmax.in");
    f>>n;
    long long v[n],m[n],maxim = 0,s;
    for (i=0;i<n;i++) {
        f>>v[i];
        m[i] = 0;
    }
    f.close();
    for (i=0;i<n-1;i++) {
        if (!m[i]) m[i]++;
        h = m[i];
        s = v[i];
        for (j=i+1;j<n;j++) {
            if (v[j] > v[i] && v[j] > s && m[j] < h + 1) {
                m[j] = h + 1;
                h++;
                s = v[j];
            }
            else {
                if (v[j] > v[i] && v[j] < s && m[j] < h + 1) {
                    h = m[i];
                    m[j] = h + 1;
                    s = v[j];
                    h++;
                }
            }
            if (maxim < m[j]) {
                maxim = m[j];
                maxpos = j;
            }
        }
    }
    if (maxpos == -1) maxpos = 0;
    ofstream g("scmax.out");
    g<<m[maxpos]<<endl;
    i = maxpos;
    while (maxim) {
        while (m[i] != maxim) i--;
        st.push(v[i]);
        maxim--;
    }
    while (!st.empty()) {
        g<<st.top()<<" ";
        st.pop();
    }
    g.close();
    return 0;
}