11456 - Trainsorting

#include<iostream>
#include<vector>
#include<cstdio>
#define MAXINT 2134483647
using namespace std;

vector< int > Seq;
vector< int > Len,LISLen,LDSLen;

void LIS(int);
void LDS(int);
int Calc(int);

int main()
{
    int t,n,i;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);

    while(t--)
    {
        scanf("%d",&n);
        Seq = vector< int >(n+1);
        Len = vector< int >(n+1);
        LISLen = vector< int >(n+1);
        LDSLen = vector< int >(n+1);

        for(i = n;i > 0;i--)
            scanf("%d",&Seq[i]);

        LIS(n);
        LDS(n);

        n = Calc(n);
        printf("%d\n",n);
    }
    return 0;
}

void LIS(int n)
{
    int i,k,tmp;
    for(i=0;i<=n;i++)
        LISLen[i] = 0;

    for(k = 1;k <= n; k++)
    {
        for(i = k-1; i>=0; i--)
        {
            tmp = 1 + LISLen[i];
            if(Seq[k] > Seq[i] && LISLen[k] < tmp)
                LISLen[k] = tmp;
        }
    }
}

void LDS(int n)
{
    int i,k,tmp;
   
    Seq[0] = MAXINT;
    for(i=1;i<=n;i++)
        LDSLen[i] = 0;

    for(k = 1;k <= n; k++)
    {
        for(i = k-1; i>=0; i--)
        {
            tmp = 1 + LDSLen[i];
            if(Seq[k] < Seq[i] && LDSLen[k] < tmp)
                LDSLen[k] = tmp;
        }
    }
}

int Calc(int n)
{
    int i,tmp,max = 0;

    for(i=1;i<=n;i++)
    {
        tmp = LISLen[i] + LDSLen[i];
        if(max<tmp)
            max = tmp;
    }

    if(max)return max-1;
    return 0;
}