Dynamic programming -- gliding wing of the strange thief Kidd

Title Description

Kidd is a legendary robber , A super thief who specializes in jewelry .

And what stands out most about him is , That is, he can escape the heavy siege of Zhongcun police department every time , And this is largely due to his easy to operate glider .

one day , Strange thief Kidd stole a precious diamond as usual , Unexpectedly, Conan children saw through the disguise , The power unit of his glider wing was also damaged by Conan's football .

I have to , The rogue Kidd can only operate the damaged glider wing to escape .

Suppose there are... In the city N The buildings line up , The height of each building is different .

At the beginning , Kidd can be on the top of any building .

He can choose one direction to escape , But you can't change direction halfway （ Because the Zhongsen police department will pursue behind ）.

Because the glider power unit is damaged , He can only slide down （ namely ： Can only glide from higher buildings to lower buildings ）.

He wants to pass the tops of different buildings as much as possible , This will slow down the impact of descent , Reduce the possibility of injury .

Excuse me, , The maximum number of different buildings he can pass through ( Including the initial building )？

Input format

The first line of input data is an integer K, On behalf of K Group test data .

Each set of test data contains two lines ： The first line is an integer N, On behalf of N Building . The second line contains N Different integers , Each corresponds to the height of a building h, According to the order of buildings .

Output format

For each set of test data , Output one line , Contains an integer , Represents the maximum number of buildings Kidd can pass through .

Data range

$1\le K\le 100$
$1\le N\le 100$
$0<h<10000$

Examples

sample input

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

sample output

6
6
9

---

Ideas – Dynamic programming

The question ： The prototype of this problem is the longest ascending subsequence . It means ： Find the longest subsequence with decreasing height , It can be understood as finding the longest descending subsequence in the array .

You can choose any position as the starting position , But you can only run in one direction , And you can't change direction halfway .

seek ： The maximum number of buildings you can pass through .

analysis ：

For the first ① In one case ：

For the first ③ In this case, it is similar to the first one . It just needs to cycle from back to front , The first ② In this case, the ①、③ Introduction ！

therefore ： The length of the longest descent subsequence can be solved from front to back 、 The length of the longest descent subsequence is calculated from back to front . Take one of the two max, Is the maximum length of the starting point at this point .

---

C++ Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int a[N], f[N];
int n; 

int main()
{
    int t;
    cin >> t;
    
    while (t --)
    {
        cin >> n;
        for (int i = 1; i <= n; i ++) cin >> a[i];
        
        int res = 0;
        for (int i = 1; i <= n; i ++)
        {
            f[i] = 1;
            for (int j = 1; j < i; j ++)
                if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
        
        for (int i = 1; i <= n; i ++) res = max(res, f[i]);
        
        for (int i = n; i >= 1; i --)
        {
            f[i] = 1;
            for (int j = n; j > i; j --)
                if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
        
        for (int i = 1; i <= n; i ++) res = max(res, f[i]);
        
        cout << res << endl;
    }
    
    return 0;
    
}