1008 拦截导弹2

#include<iostream>
using namespace std;

// Longest Decreasing Subsequence problem
int LDS(int a[], int num)
{
    int lds[num];
    int max = 0;
    for (int i = 0; i < num; i++)
    {
        lds[i] = 1;
    }
    for (int i = 1; i < num; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[i] < a[j] && lds[i] < lds[j] + 1)
            {
                lds[i] = lds[j] + 1;
            }
        }
    }
    for (int i = 0; i < num; i++)
    {
        if (max < lds[i])
        {
            max = lds[i];
        }
    }
    return max;
}

int greedy(int a[], int num)
{
    // height[i]表示第i个系统能够发射的最大高度
    int height[num];
    // count用来计数
    int count=0,min_idx=0;

    height[0] = a[0];
    for(int i=1;i<num;i++)
    {
        if(a[i]>height[count]){
            height[++count]=a[i];
        }
        else{
            min_idx=count;
            for(int j=count;j>=0;j--)
            {
                //所有系统中发射高度最矮的那套来拦截
                if(height[j]<height[min_idx] && height[j]>=a[i])
                {
                    min_idx=j;
                }
            }
            height[min_idx]=a[i];
        }
    }
    return count+1;
}

int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        int num;
        cin>>num;
        int a[num];
        for(int j=0;j<num;j++)
        {
            cin>>a[j];
        }
        cout<<LDS(a, num)<<" "<<greedy(a, num)<<endl;
    }   
    return 0;
}