World's most popular travel blog for travel bloggers.

[Solved]: Find subsequence of maximal length simultaneously satisfying two ordering constraints

, ,
Problem Detail:

We are given a set $F=\{f_1, f_2, f_3, …, f_N\}$ of $N$ Fruits. Each Fruit has price $P_i$ and vitamin content $V_i$; we associated fruit $f_i$ with the ordered pair $(P_i, V_i)$. Now we have to arrange these fruits in such a way that the sorted list contains prices in ascending order and vitamin contents in descending order.

Example 1: $N = 4$ and $F = \{(2, 8), (5, 11), (7, 9), (10, 2)\}$.

If we arrange the list such that all price are in ascending order and vitamin contents in descending order, then the valid lists are the following:

• $[(2, 8)]$
• $[(5, 11)]$
• $[(7, 9)]$
• $[(10, 2)]$
• $[(2, 8), (10, 2)]$
• $[(5, 11), (7, 9)]$
• $[(5, 11), (10, 2)]$
• $[(7, 9), (10, 2)]$
• $[(5, 11), (7, 9), (10, 2)]$

From the above lists, I want to choose the list of maximal size. If more than one list has maximal size, we should choose the list of maximal size whose sum of prices is least. The list which should be chosen in the above example is $\{(5, 11), (7, 9), (10, 2)\}$.