LeetCode 2407 Longest Increasing Subsequence II - Why Naive Fails

Standard LIS DP is $O(n^2)$. The constraint that consecutive elements differ by at most $k$ doesn't reduce this with naive approach.

Example: $n = 10^5$, $k = 10^5$. Standard LIS checks all $j < i$ where $nums[j] < nums[i]$. Still $O(n^2)$.

Segment tree: for element with value $v$, query max LIS among values $[v-k, v-1]$. Add $1$ for current element. Update segment tree at position $v$. Each operation is $O(\log(\max(nums)))$.