Cod sursa(job #1929844)

Utilizator Lungu007Lungu Ionut Lungu007 Data 18 martie 2017 10:51:02
Problema Subsir 2 Scor 45
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,ult;


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

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


            }
        }
//        if(d[i] == NMAX) {
//            pre[i] = 0;
//            d[i] = 1;
//        }
    }

    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=pos;i!=0;i = pre[i]) {
        out << i << " ";
    }
    return 0;
}