Solution

Method 1 – Segment Tree Dynamic Programming

Intuition

To efficiently find the longest increasing subsequence with adjacent difference at most k, we use a segment tree (or binary indexed tree) to keep track of the maximum dp value for all possible previous numbers in the valid range. For each number, we query the segment tree for the best previous result and update the tree with the new dp value.

Approach

Coordinate-compress the values in nums to allow efficient segment tree indexing.
Initialize a segment tree to support range maximum queries and point updates.
For each number x in nums:
- Query the segment tree for the maximum dp value in the range [x-k, x-1].
- Set dp[x] = max_query + 1.
- Update the segment tree at position x with dp[x].
The answer is the maximum value in the dp array.

Code

[{"language":"C++","code":"class SegmentTree {\n    vector<int> tree;\n    int n;\npublic:\n    SegmentTree(int size) : n(size), tree(2*size) {}\n    void update(int i, int val) {\n        i += n;\n        tree[i] = max(tree[i], val);\n        for (i /= 2; i > 0; i /= 2)\n            tree[i] = max(tree[2*i], tree[2*i+1]);\n    }\n    int query(int l, int r) {\n        int res = 0;\n        for (l += n, r += n; l < r; l /= 2, r /= 2) {\n            if (l%2) res = max(res, tree[l++]);\n            if (r%2) res = max(res, tree[--r]);\n        }\n        return res;\n    }\n};\nclass Solution {\npublic:\n    int lengthOfLIS(vector<int>& nums, int k) {\n        set<int> s(nums.begin(), nums.end());\n        vector<int> vals(s.begin(), s.end());\n        unordered_map<int, int> idx;\n        for (int i = 0; i < vals.size(); ++i) idx[vals[i]] = i;\n        SegmentTree st(vals.size());\n        int ans = 0;\n        for (int x : nums) {\n            int l = lower_bound(vals.begin(), vals.end(), x-k) - vals.begin();\n            int r = lower_bound(vals.begin(), vals.end(), x) - vals.begin();\n            int best = st.query(l, r);\n            int cur = best + 1;\n            st.update(idx[x], cur);\n            ans = max(ans, cur);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> SegmentTree</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">    vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> tree;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><

Related Tags

Continue Practicing