这是《破解编码面试》一书中的问题:
\n\n马戏团正在设计一种塔式表演,由人们相互站立\xe2\x80\x99s\n肩膀组成。出于实用和美观的原因,每个人都必须比他或她下面的人矮且轻。给定马戏团中每个人的身高和体重,编写一个方法来计算这样一座塔中的最大可能人数。
\n\n例子:
\n\n输入:
\n\n(ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) \nRun Code Online (Sandbox Code Playgroud)\n\n输出:
\n\n最长的塔长 6,从上到下包括:
\n\n(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)\nRun Code Online (Sandbox Code Playgroud)\n\n这是书上的解决方案:
\n\n“当我们剔除这个问题的所有废话时,我们就能明白问题实际上是以下这样的。
\n\n我们有一个成对的项目列表。找到最长的序列,使得第一项和第二项都按非递减顺序排列。”
\n\n我想出了这个例子:
\n\n {1,1} \n {3,3} {7,2}\n{6,4} {9,9} {8,5}\nRun Code Online (Sandbox Code Playgroud)\n\n在这里,序列的值不是按非递减顺序排列的,但它仍然是一个有效的塔。而且我找不到一种方法将相同的物品组织到另一个塔中,该塔的物品按非递减顺序排列。我相信没有这样的办法。所以在我看来,这个解决方案是不正确的。
\n\n我错过了什么吗?
\n\n提前致谢。
\n