解决阿里巴巴编程题：最长递增子序列优化

"2021阿里巴巴编程题.md" 这篇编程题目是关于寻找物品子集的最大数量，满足特定条件的问题，即子集中任意两个物品的属性 xi 和 yi 满足以下关系：xi < xj 且 yi < yj 或者 xi > xj 且 yi > yj。这个问题可以通过最长递增子序列 (Longest Increasing Subsequence, LIS) 的方法来解决。 首先，题目要求的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。在这个问题中，n 表示物品的数量。 代码中首先对输入的二维数组 arr 进行排序。这里采用了自定义比较器，使得当第一个属性相同时，按照第二个属性降序排列。这样做的目的是为了方便后续的最长递增子序列计算。 接下来，代码创建了一个新的数组 nums，用于存储 arr 中第二个属性的值。然后，通过遍历 nums，找到其最长递增子序列。这里运用了二分查找法更新 tails 数组，tails[k] 存储了长度为 k+1 的递增子序列的尾部元素值。二分查找可以快速定位新元素在 tails 数组中的位置，从而保持 tails 数组的有序性。 在二分查找过程中，变量 left 和 right 分别表示搜索范围的左边界和右边界，初始化时，right 设置为 tails 数组的当前长度 res 而不是 length-1，因为我们要查找的是尾巴元素的位置。如果 tails[mid] 小于新元素 num，则左边界移动到 mid+1；否则，右边界移动到 mid。这样，当 left 和 right 相等时，找到了合适的位置。 最后，将 num 插入到 tails 数组的正确位置，并检查是否需要扩展 tails 数组的长度。res 变量记录了当前最长递增子序列的长度，也是满足条件的物品最大数量。 在主函数 main 中，程序读取数据组数 p，然后对于每组数据，读取物品数量 n 和各物品的属性，调用 maxGoods 函数求解，并输出结果。 这个编程题考察了排序、自定义比较器、以及最长递增子序列的动态规划求解技巧，这些都是数据结构与算法中的核心知识点。在实际编程面试或工作中，这类问题能够检验应聘者的逻辑思维和算法实现能力。