有大佬能帮我找一下特殊用例吗，这个只有20分

Han_feng @ 2024-01-05 22:58:48

#include<stdio.h>
#include<string.h>
int main(void){
    int n,i,j;
    scanf("%d",&n);
    int num[n],region[n];
    region[0]=1;
    for(i=0;i<n;i++)
        scanf("%d",num+i);
    for(i=1;i<n;i++){
        int max=0;
        region[i]=1;
        for(j=0;j<i;j++)
            if(num[j]<num[i]&&num[j]>max){
                max=num[j];
                region[i]=region[j]+1>region[i]?region[j]+1:region[i];
            }
        region[i]=region[i]>region[i-1]?region[i]:region[i-1];
    }
    printf("%d\n",region[i-1]);
    return 0;
}

by Zemu_Ooo @ 2024-01-05 23:10:44

@Han_feng

首先第一眼看到 O(n^2) 的算法，就知道对于 n \leq 5000 的数据规模是根本跑不动的（

其次，没看懂为什么要在更新 region[i] 时，将其与 region[i-1] 进行比较，题意只需要找到以 num[i] 结尾的最长上升子序列，而不需要考虑它与前一个元素的关系。

我大致按照我的码风修改了一下，你可以稍微参考：

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
    int n;
    scanf("%d", &n);
    vector<int> num(n), dp;

    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), num[i]);
        if (it == dp.end()) {
            dp.push_back(num[i]);
        } else {
            *it = num[i];
        }
    }

    printf("%d\n", dp.size());
    return 0;
}

by Zemu_Ooo @ 2024-01-05 23:12:14

如果真的按照你的代码逻辑思考，大概是这样的（因为那一版用了些指针，但是对于这题而言感觉没啥必要）：

#include <stdio.h>
#include <string.h>
int main(void) {
    int n, i, j;
    scanf("%d", &n);
    int num[n], dp[n]; 
    for (i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        dp[i] = 1; 
    }
    int max_length = 1;
    for (i = 1; i < n; i++) {
        for (j = 0; j < i; j++) {
            if (num[j] < num[i]) {
                dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i];
            }
        }
        max_length = dp[i] > max_length ? dp[i] : max_length;
    }
    printf("%d\n", max_length);
    return 0;
}

by Han_feng @ 2024-01-05 23:25:32

@Zemu_Ooo 谢谢，我再想一下