Leetcode 2407. Longest Increasing Subsequence II
Find the length of the longest strictly increasing subsequence of nums such that each adjacent difference is ≤ k. With n up to 1e5 and values bounded, this reduces to DP where dp[x] = 1 + max dp[y] for y in [x-k, x-1], requiring a range-maximum data structure (segment tree / Fenwick) for efficiency.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
All Regions
Late December, 2024
Mid-level
Longest Increasing Subsequence II
Hello Interview Premium
Your account is free and you can post anonymously if you choose.