问题分析

该问题描述了晶圆厂中芯片上连接两个功能模块端口的信号交叉情况，工程师需要找出在芯片表面上不相互交叉的信号的最大数量。给定每个测试场景中右侧功能模块上连接到左侧功能模块的端口号序列，通过这些端口号来确定不交叉信号的最大数量。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;

int t, n, s[40010];
int dp[40010];

int main() {
    scanf("%d", &t);
    while (t--) {
        memset(dp, inf, sizeof(dp));
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++)
            scanf("%d", &s[i]);
        
        for (int i = 0; i < n; i++)
            *lower_bound(dp, dp + n, s[i]) = s[i];
        printf("%d\n", lower_bound(dp, dp + n, inf) - dp);
    }
    return 0;
}

复杂度分析

1. 时间复杂度：

   • 外层循环处理每个测试用例，时间复杂度为 (O(t)) ，其中 (t) 是测试用例的数量。
   • 对于每个测试用例，读取端口号序列的时间复杂度为 (O(n)) ，其中 (n) 是端口数量。

2. 空间复杂度：

   • 使用了 s 数组和 dp 数组来存储端口号序列和最长递增子序列的状态，空间复杂度为 (O(n)) ，其中 (n) 是端口数量。