hrbeu 하 엔지니어링 Who Is In Front of Me

//DP              
//     pre  ，     KMP     next  


#include <stdio.h>

#include <string.h>

#define MAX 50100

int a[MAX],pre[MAX],dp[MAX];

int n;

int main()

{

        int i,j,T,max;

        scanf("%d",&T);

        while(T--)

        {

                scanf("%d",&n);

                pre[1]=0;  dp[1]=0;

                scanf("%d",&a[1]);

                max=0;

                for(i=2; i<=n; i++)

                {

                        scanf("%d",&a[i]);

                        if(a[i]<a[i-1]) 

                        {

                                pre[i]=i-1;

                                dp[i]=dp[i-1]+1;

                        }

                        else

                        {

                                for(j=pre[i-1]; j!=0 && a[i]>=a[j] ; j=pre[j]) ;

                                pre[i]=j;

                                if(!pre[i])  dp[i]=0;

                                else         dp[i]=dp[pre[i]]+1;

                        }

                        max=dp[i]>max?dp[i]:max;

                }



//              for(i=1; i<=n; i++) printf("%d ",pre[i]); printf("
");

//              for(i=1; i<=n; i++) printf("%d ",dp[i]);  printf("
");

                printf("%d
",max);

        }

        return 0;

}