Cod sursa(job #1327105)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 26 ianuarie 2015 13:17:22
Problema Secv Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>
int maxpos;
int lis( int arr[], int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );
   for ( i = 0; i < n; i++ ) lis[i] = 1;
   for ( i = 1; i < n; i++ )
   {
       for ( j = 0; j < i; j++ )
       {
           if ( arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1;
       }
   }
   for ( i = 0; i < n; i++ )
   {
       if ( max < lis[i] ) 
       {
            max = lis[i];
            maxpos=i;
       }
   }
   free( lis );
   return max;
}
int main()
{
    freopen ("secv.in","r",stdin);
    freopen ("secv.out","w",stdout);
    int n;
    scanf("%d",&n);
    int ma=0,a[5001];
    for(int i=0;i<n;i++) 
    {
            scanf("%d",&a[i]);
            if(ma<a[i]) ma=a[i];
    }
    int max=lis(a,n);
    if(max!=ma) printf("-1");
    else
    {
        for(int i=maxpos-max+1;i>=1;i--)
        {
                if(a[i]==1) 
                {
                            printf("%d\n",maxpos-i+1);
                            break;
                }
        }
    }
}