algorithm - 打印最大列表

Question

给定 N 个水果的集合 F={a1,a2,a3,…,aN}。每个水果都有价格 Pi 和维生素含量 Vi。现在我们必须以这样的方式排列这些水果，列表包含价格升序，列表包含维生素降序排列。

例如:: N=4

圆周率：2 5 7 10

六：8 11 9 2

这是确切的问题https://cs.stackexchange.com/questions/1287/find-subsequence-of-maximal-length-simultaneously-satisfying-two-ordering-constr/1289#1289

Answer 1

我会尝试将问题减少到最长增加的后续问题。

1. 根据第一个标准对列表进行排序 [维生素]
2. 然后，根据第二个标准[价格]，在修改后的列表中找到最长的后续

这个解决方案是O(nlogn)，因为步骤 (1) 和 (2) 都可以在O(nlogn)每个中完成。
看看维基百科的文章，在高效算法下- 你如何实现最长的后续增加

编辑：

如果您的列表允许重复，则您的排序 [步骤 (1)] 将必须按第二个参数作为次要标准进行排序，以防主要标准相等。

示例[您的示例 2]：

Pi::99 12 34 10 87 19 90 43 13 78
Vi::10 23 4 5 11 10 18 90 100 65

在第 1 步之后，您会得到 [排序何时Vi是主要标准，降序]：

Pi:: 013 43 78 12 90 87 87 99 10 34
Vi:: 100 90 65 23 18 11 10 10 05 04

第二步找到 Pi 中最长的递增子序列，你得到：

(13,100), (43,90), (78,65), (87,11), (99,10)

作为一种可行的解决方案，因为它是排序列表中的递增子序列 [根据Pi]。

PS在这里我假设你想要的增加的子序列是严格增加的，否则结果是(13,100),(43,90),(78,65),(87,11),(87,10),(99,10)- 这是更长的子序列，但它不是根据Pi和严格增加/减少Vi