题目描述： 全班N（2<=N<=45）个人排成一排，但因为高矮不齐，需要进行调整。调整的方法是，不调换左右次序，只让若干人后退一步变为第2排，使第一排留下的人从左到右的身高按降序排列，即右边的人不比左边的人高。如果第2排的人还不按降序排列，则照此办理，即再让第2排的若干人后退一步变为第3排，这样继续下去，直到所有排的人都按身高从高到低排列。现在将每个人的身高保存在列表L中，给你L，请你找出一种使第一排留下的人数尽可能多的调整方法，输出第一排留下的人数P及最后调整完共有几排数K，P和K之间以一个空格隔开。
如，L=[130, 122, 112, 126, 126, 125, 120, 100], 则输出6 2。
示例： 输入： L = [130, 122, 112, 126, 126, 125, 120, 100] 输出： 6 2
分析: 这个题目我们分析一下，实际上是两个问题：
- 最长非递增子序列；
- 导弹拦截系统（acm）； —- 这是一个 动态规划问题。
问题一： 最长非递增子序列
假设 nums[i] 是 以第 i 个元素结尾的最长子序列长度为 nums[i] 。
如何求 nums[i] 呢？
- 令 nums[i] = 1。 表示只有 它 自己一个元素。
- 依次和前 i - 1 个元素做比较。
- 如果 nums[i] > nums[j]， 则表示 第 i 个 元素，不能接在 第 j 个元素的后面。
- 如果 nums[i] <= nums[j], 则表示 第 i 个元素可以接在第 j 元素的后面，nums[i] = max(nums[i], nums[j] + 1)
1
2
3
4
5
6
7
8
9
nums = [1 for _ in L]
for i in range(1, len(L)):
for j in range(0, i):
if L[i] <= L[j]:
nums[i] = max(nums[i], nums[j]+1)
ans = max(nums)
问题二： 导弹拦截系统（acm）
导弹拦截系统：有不同高度的导弹飞过来，现在导弹拦截系统对这些导弹进行拦截，但是这个拦截系统有bug，每次拦截的高度不能高于上一次拦截的高度，问拦截所有导弹需要至少需要几套这样的系统？
算法：
- 首先将所有导弹标记为 未拦截。
- 开始遍历所有导弹
- 导弹状态 已拦截 ，那就没事。
- 导弹状态 未拦截。则判断当前导弹的高度和当前拦截系统的高度。拦截以后都将把导弹标记为 已拦截
- 如果导弹高度 > 当前拦截系统高度，则需要一个新的拦截系统，并且新的拦截系统的最大高度就是当前导弹的高度。
- 如果 导弹高度 <= 当前拦截系统高度，则当前导弹拦截系统的高度变为当前导弹的高度。
1
2
3
4
5
6
7
8
9
10
nums = [0 for _ in L]
res = 0
for index, value in enumerate(L):
if not nums[index]:
res += 1
for j in range(index+1, len(L)):
if L[j] <= value:
value = L[j]
nums[j] = 1
再好好想想，其实这个导弹拦截系统问题，和我们的题目问题实际上是一样的，一排不行就下一排，一套系统不行就新一套系统。 并且都是从高到低。
虽然题目要求第一排站的人要足够多，但是不管怎样最终站多少排是固定的。
你品，你细品。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
nums = [1 for _ in L]
for i in range(1, len(L)):
for j in range(0, i):
if L[i] <= L[j]:
nums[i] = max(nums[i], nums[j]+1)
ans = max(nums)
nums = [0 for _ in L]
res = 0
for index, value in enumerate(L):
if not nums[index]:
res += 1
for j in range(index+1, len(L)):
if L[j] <= value:
value = L[j]
nums[j] = 1
print(ans, res)