Find the Longest Valid Obstacle Course at Each Position
You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.
For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles[0..i] such that:
- You choose some subset of obstacles between
0andiinclusive. - You must include
obstacles[i]as the last obstacle in the course. - The selected obstacles must be in non-decreasing order of height.
Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.
Examples
Input: [1,2,3,2]
Output: [1,2,3,3]
Input: [2,2,1]
Output: [1,2,1]
Hints
Start by understanding that for each index `i`, you need to find the longest non-decreasing subsequence ending at `obstacles[i]` in the subarray `obstacles[0..i]`. Think about how you can leverage previous results to compute the current one efficiently.
Consider using dynamic programming where `dp[i]` represents the length of the longest obstacle course ending at `obstacles[i]`. To compute `dp[i]`, you need to find the maximum `dp[j]` for all `j < i` where `obstacles[j] <= obstacles[i]`, and then set `dp[i] = max(dp[j]) + 1`.
To optimize the solution, observe that the problem reduces to finding the length of the longest non-decreasing subsequence ending at each position. This can be efficiently solved using a modified version of the patience sorting algorithm (similar to the approach used in the "Longest Increasing Subsequence" problem), where you maintain a list of the smallest possible tail values for all increasing subsequences of various lengths encountered so far. Use binary search to update this list for each `obstacles[i]`.
Find the Longest Valid Obstacle Course at Each Position
You want to build some obstacle courses. You are given a 0-indexed integer array `obstacles` of length `n`, where `obstacles[i]` describes the height of the `i`th obstacle.