分解为最长上升子序列和最长下降子序列

import java.util.*;
public class Main{
    static int N=110;
    static int []a=new int [N];
    //最长下降子序列
    static int []r=new int [N];
    //最长上升子序列
    static int []l=new  int [N];
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            for(int i=1;i<=n;i++)a[i]=sc.nextInt();
            int res=0;
            for(int i=1;i<=n;i++){
                l[i]=r[i]=1;
                for(int j=1;j<i;j++){
                    if(a[j]<a[i])l[i]=Math.max(l[i],l[j]+1);
                    if(a[j]>a[i])r[i]=Math.max(r[i],r[j]+1);
                }
                res=Math.max(res,l[i]);
                res=Math.max(res,r[i]);
            }
            System.out.println(res);
        }
    }
}