Longest Increasing Subsequence With Bounded Adjacent Difference
HardAsked in:Amazon•Stage:Onsite
arraydynamic_programmingsegment_tree
Problem Statement
Given an array of n integers and an integer K, find the length of the longest strictly increasing subsequence such that the absolute difference between any two consecutive elements in the subsequence does not exceed K.
Input Format
The first line contains two integers n and K (1 ≤ n ≤ 10^5, 0 ≤ K ≤ 10^9). The second line contains n space‑separated integers a1,…,an (|ai| ≤ 10^9).
Output Format
Print a single integer – the maximum possible length of a subsequence satisfying the conditions.
Constraints
- 1 <= n <= 10^5
- 0 <= K <= 10^9
- |ai| <= 10^9