打印最大值列表

我們給出N個水果的集合F = {a1，a2，a3，...，aN}。每個水果的價格都是Pi和維生素含量Vi.Now我們必須按照這樣的方式安排這些水果，以便列表中的價格按升序排列，而列表中含有按降序排列的維生素。打印最大值列表

例如:: N = 4

裨：2 5 7 10

維：8 11 9 2

2012-04-15 John Greve

該解決方案是O(nlogn) ，因爲步驟（1）和（2）都可以在O(nlogn)中完成。
對維基百科的文章一看，Efficient Algorithms下 - 如何可以實現最長遞增隨後

編輯：

如果列表允許重複，你的排序[步驟（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]在排序列表中。

P.S.在這裏，我假設你想要增加的子序列是嚴格增加，否則結果是(13,100),(43,90),(78,65),(87,11),(87,10),(99,10) - 這是更長的子序列，但它不是嚴格增加/減少根據Pi和Vi

2012-04-15 11:03:22 amit

：我認爲它應該是最長的減少子序列。但是你上面的答案，例如2 – 2012-04-15 11:22:43

@JohnGreve：看看編輯，我澄清了它。請注意，如果按'Vi'作爲主要標準[降序]排序，然後根據'Pi'查找增加的子序列，並且您正在尋找減少的子序列，則您正在尋找最長的子序列，反之亦然。 – amit 2012-04-15 13:51:01

P.S.在這裏，我假設你想增加的子序列是嚴格增加的，否則結果是（13,100），（43,90），（78,65），（87,11），（87,10），（99， 10）' - 這是更長的子序列，但它並不嚴格按照「Pi」和「Vi」進行增減 – amit 2012-04-15 14:00:31

回答