经典算法：最长递增子序列

配合题目：

5841. 找出到每个位置为止最长的有效障碍赛跑路线

题目要求：对于输入数组的每个元素，输出包含该元素、并以该元素为结尾的最长递增子序列的长度，即每个。（本题中的递增：  n[i-1] ≤ n[i]）

方法一：动态规划

定义ans数组，ans[i]为以num[i]为结尾的“最长递增子序列”的长度，则有：

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: list[int]) -> list[int]:
        n = len(obstacles)
        ans = [None] * n
        for i in range(n):
            if i == 0:
                ans[0] = 1
            else:
                o = obstacles[i]
                ans[i] = max((ans[j] for j in range(i) if obstacles[j] <= o), default = 0) + 1
        return ans
           

时间复杂度为 

，此解法超时。

方法二：动态规划 + 贪心优化

贪心思路是：如果想子序列最长，也等价于达成长度L时结尾元素尽量小

用状态数组 d[] 保存：d[i] 是长度为 i 的“最长递增子序列”的末尾元素的最小值

根据定义可知：d[] 是有序的，可以用二分优化访问

import bisect
class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: list[int]) -> list[int]:
        d = []
        ans = []
        for o in obstacles:
            if not d or o >= d[-1]:
                d.append(o)
                ans.append(len(d))
            else:
                loc = bisect.bisect_right(d, o)
                ans.append(loc + 1)
                d[loc] = o
        return ans
           

时间复杂度为 

，此解法通过。