Cod sursa(job #1337292)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 8 februarie 2015 20:31:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#define FIN "scmax.in"
#define FOUT "scmax.out"
#define maxsize 100002
using namespace std;

long long v[maxsize];
int l[maxsize];
int n;

void read()
{
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &n);

    for(int i=1;i<=n;i++)
        scanf("%lld ", &v[i]);

}

void solve()
{

    l[n] = 1;

    for(int i=n-1;i>0;i--)
    {
        int maxLen = l[i];
        int son = i;
        for(int j=i+1;j<=n;j++)
        {
            if(v[i] < v[j])
            {
                if(maxLen < l[j] )
                {
                    maxLen = l[j];
                    son = j;
                }
            }
        }

        l[i] = 1 + maxLen;

    }


}

void write()
{
    int maxLen = l[1];
    int maxPos = 1;
    for(int i=2;i<=n;i++)
    {
        if(maxLen < l[i])
        {
            maxLen = l[i];
            maxPos = i;
        }

    }

    printf("%d \n", maxLen);
    printf("%d ", v[maxPos]);

  for(int i=maxPos+1; i <= n; i++)
  {
      if(v[i] > v[maxPos] && l[i] == maxLen-1)
      {
          printf("%d ", v[i]);
          maxLen--;
      }

  }

}

int main()
{
    read();
    solve();
    write();
    return 0;
}