最长上升字串

coding>C++
817 词

题目描述

给定n个整数，对其进行m次查询。每次查询是一个范围l到r，求出l到r的最长上升连续子串。上升连续子串的定义为一个连续的子串且严格递增。

输入

第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n,m，代表有一共有n个人，m个查询。第二行共有n个整数，接下来m行是m次查询，每行两个整数l,r。

输出

共T行，每行m个整数，代表最长上升连续字串。其中$T<=50$,$m<1e5$,每个数的大小不超过1e9。

样例输入

1
2
3
4
5
1
4 2
3 2 4 5
1 3
1 4

样例输出

1
2 3

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int main() {
    int T, n, m;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        int num[n + 10], search[n + 10][2], dp[n + 10];
        fill(dp, dp + n, 0);
        for (int i = 1; i <= n; ++i)
            cin >> num[i];
        for (int i = 0; i < m; ++i) {
            cin >> search[i][0] >> search[i][1];
            int ans = 0;
            for (int j = search[i][0]; j <= search[i][1]; j++) {
                dp[j] = 1;
                for (int k = search[i][0]; k < j; k++)
                    if (num[k] < num[j] && j - k == 1) dp[j] = max(dp[j], dp[k] + 1);
                ans = max(ans, dp[j]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}