有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110] 输出：6 解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
分析： 首先对身高进行排序，那么此问题就演变成了找体重的最长递增子序列问题，通过DP算法求解，由于此题是需要体重和身高严格递增，也就是不能存在相等的情况，那么对身高进行升序排序后，在身高相同的情况下需要对体重进行降序排序，也就是说在身高相同的这个区间中，体重最多只有一个取值满足递增子序列的要求，对于以第i处体重结尾的序列dp[i] = max(dp[j]+1, dp[i]), 其中j取值范围为[0,i]
方法1： dp求解最长递增子序列， 时间复杂度
O
(
n
2
)
O(n^2)
O(n2)
class Solution:
def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
new_array = [[height[i], weight[i]] for i in range(len(height))]
#对身高进行降序排序，在身高相同的情况下，对体重升序排序
new_array = sorted(new_array, key=lambda x:（x[0],-x[1]), reverse=True)
dp_array = [0]*len(new_array)
dp_array[0] = 1
for i in range(1, len(new_array)):
max_num = 1
for j in range(i):
if new_array[i][1] < new_array[j][1]:
max_num = max(max_num, dp_array[j]+1)
dp_array[i] = max_num
return max(dp_array)
方法2： 由于方法1超时，因此需要对dp算法进行优化，采用二分查找的方法求最长递增子序列， 时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
https://blog.csdn.net/u012505432/article/details/52228945
class Solution:
def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
new_array = [[height[i], weight[i]] for i in range(len(height))]
new_array = sorted(new_array, key=lambda x:(x[0], -x[1]), reverse=True)
# print(new_array)
tail = []
tail.append(new_array[0][1])
for i in range(1, len(new_array)):
l, r = 0, len(tail)-1
# print(tail)
if new_array[i][1] < tail[-1]:
tail.append(new_array[i][1])
continue
while l <= r:
mid = (l+r)//2
if tail[mid] <= new_array[i][1]:
r = mid - 1
else:
l = mid + 1
tail[l] = new_array[i][1]
return len(tail)
