3053: 怪盗基德的滑翔翼 最长递增或递减子序列

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量k, n和数组a, dp, dp2，大小为110
int k, n, a[110], dp[110], dp2[110];
int main() {
    // 读取测试用例的数量k
    cin >> k;
    // 循环处理每个测试用例
    while (k--) {
        // 读取当前测试用例的数组长度n
        cin >> n;
        // 读取数组a的元素并初始化dp和dp2数组
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            dp[i] = 1;
            dp2[i] = 1;
        }
        // 动态规划计算最长递减和递增子序列的长度
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (a[i] < a[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                if (a[i] > a[j]) {
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }
        // 找到dp和dp2中的最大值
        int kkk = -1;
        for (int i = 1; i <= n; i++) {
            kkk = max(kkk, dp[i]);
            kkk = max(kkk, dp2[i]);
        }
        cout << kkk << endl;
    }
    return 0;
}