Cod sursa(job #1929594)

Utilizator Lungu007Lungu Ionut Lungu007 Data 17 martie 2017 20:09:15
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
#define NMAX 5002
using namespace std;

ifstream in("subsir2.in");
ofstream out("subsir2.out");

int a[NMAX],d[NMAX],pre[NMAX],n;

void af(int pos) {
//for(int i=pos;i!=0;i = pre[i]) {
//        out << i << " ";
//    }
    if(pos == 0)
     return;

     af(pre[pos]);
     out << pos << " ";

}

int main()
{
    in >> n;
    for(int i=1;i<=n;i++) {
        in >> a[i];
    }
    d[1] = 1;

    for(int i=1;i<=n;i++) {
        for(int j=1;j<i;j++) {
            if(a[j]<=a[i]) {
                if(d[j]+1 > d[i]) {
                    d[i] = d[j]+1;
                    pre[i] = j;
                }
                else if(d[j]+1 == d[i] && a[j] <= a[pre[i]]) {
                    pre[i] = j;
                }
            }
        }
    }

    int mx=0,pos=0;
    for(int i=1;i<=n;i++) {
        if(mx < d[i]) {
            mx = d[i];
            pos = i;
        }

        if(mx == d[i]) {
            if(a[i] < a[pos]) {
                pos = i;
            }
        }
    }
    out << mx << '\n';
//    for(int i=1;i<=n;i++) {
//        cout << pre[i] << " ";
//    }
    af(pos);
    return 0;
}