1class Solution {
2    public int lengthOfLIS(int[] nums, int k) {
3        // Find the maximum value in nums to define the size of the Segment Tree
4        int maxVal = nums[0];
5        for (int value : nums) {
6            maxVal = Math.max(maxVal, value);
7        }
8      
9        // Initialize the Segment Tree
10        SegmentTree segmentTree = new SegmentTree(maxVal);
11      
12        // Variable to keep track of the length of the Longest Increasing Subsequence (LIS)
13        int maxLength = 0;
14      
15        // Iterate through all numbers in the array
16        for (int value : nums) {
17            // Query the segment tree for the longest subsequence that ends with a number less than 'value - k'
18            int t = segmentTree.query(1, Math.max(1, value - k), value - 1) + 1;
19            maxLength = Math.max(maxLength, t); // Update the length of the LIS
20          
21            // Modify the segment tree with the new value of the LIS ending with 'value'
22            segmentTree.modify(1, value, t);
23        }
24      
25        // Return the length of the LIS
26        return maxLength;
27    }
28}
29
30class SegmentTreeNode {
31    int left;
32    int right;
33    int value;
34}
35
36class SegmentTree {
37    private SegmentTreeNode[] tree;
38
39    public SegmentTree(int size) {
40        // Initialize the segment tree array based on the size
41        tree = new SegmentTreeNode[4 * size];
42        for (int i = 0; i < tree.length; ++i) {
43            tree[i] = new SegmentTreeNode();
44        }
45        // Build the segment tree
46        build(1, 1, size);
47    }
48
49    // Recursive method to build the segment tree
50    public void build(int node, int start, int end) {
51        tree[node].left = start;
52        tree[node].right = end;
53        if (start == end) {
54            // Leaf node
55            return;
56        }
57        int mid = (start + end) >> 1;
58        build(node * 2, start, mid); // Build left child
59        build(node * 2 + 1, mid + 1, end); // Build right child
60    }
61
62    // Method to modify the segment tree at a given index
63    public void modify(int node, int index, int value) {
64        if (tree[node].left == index && tree[node].right == index) {
65            // If the current node corresponds to the index, update its value
66            tree[node].value = value;
67            return;
68        }
69        int mid = (tree[node].left + tree[node].right) >> 1;
70        // Recursively call modify on the correct child
71        if (index <= mid) {
72            modify(node * 2, index, value);
73        } else {
74            modify(node * 2 + 1, index, value);
75        }
76        pushUp(node); // Update the current node's value
77    }
78
79    // Method to push up the value to the parent node
80    public void pushUp(int node) {
81        tree[node].value = Math.max(tree[node * 2].value, tree[node * 2 + 1].value);
82    }
83
84    // Method to query the segment tree in a range [l, r]
85    public int query(int node, int start, int end) {
86        if (tree[node].left >= start && tree[node].right <= end) {
87            // If the current node is completely within the range, return its value
88            return tree[node].value;
89        }
90        int mid = (tree[node].left + tree[node].right) >> 1;
91        int maxVal = 0;
92        // Query the left and/or right child based on the range and take the maximum value
93        if (start <= mid) {
94            maxVal = query(node * 2, start, end);
95        }
96        if (end > mid) {
97            maxVal = Math.max(maxVal, query(node * 2 + 1, start, end));
98        }
99        return maxVal;
100    }
101}
102

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6// Node class representing a node in the segment tree.
7class Node {
8public:
9    int left;
10    int right;
11    int value;
12};
13
14// SegmentTree class representing a segment tree data structure.
15class SegmentTree {
16private:
17    vector<Node*> tree; // Vector of Node pointers representing the segment tree structure.
18
19    // Private helper method to push-up the value to the parent node after modifications.
20    void pushUp(int index) {
21        tree[index]->value = max(tree[index * 2]->value, tree[index * 2 + 1]->value);
22    }
23
24public:
25    // Constructor to initialize segment tree with `n` elements.
26    SegmentTree(int n) {
27        tree.resize(4 * n);
28        for (int i = 0; i < tree.size(); ++i) tree[i] = new Node();
29        build(1, 1, n);
30    }
31
32    // Method to build the segment tree recursively.
33    void build(int index, int left, int right) {
34        tree[index]->left = left;
35        tree[index]->right = right;
36        if (left == right) return; // Base case: reach a leaf node.
37        int mid = (left + right) >> 1;
38        build(index * 2, left, mid);
39        build(index * 2 + 1, mid + 1, right);
40    }
41
42    // Method to modify the value at a specific position in the segment tree.
43    void modify(int index, int position, int value) {
44        if (tree[index]->left == position && tree[index]->right == position) {
45            tree[index]->value = value;
46            return;
47        }
48        int mid = (tree[index]->left + tree[index]->right) >> 1;
49        if (position <= mid)
50            modify(index * 2, position, value);
51        else
52            modify(index * 2 + 1, position, value);
53        pushUp(index);
54    }
55
56    // Method to query the maximum value within a range [left, right] in the segment tree.
57    int query(int index, int left, int right) {
58        if (tree[index]->left >= left && tree[index]->right <= right) return tree[index]->value;
59        int mid = (tree[index]->left + tree[index]->right) >> 1;
60        int maxValue = 0;
61        if (left <= mid) maxValue = query(index * 2, left, right);
62        if (right > mid) maxValue = max(maxValue, query(index * 2 + 1, left, right));
63        return maxValue;
64    }
65};
66
67// Solution class to solve the problem.
68class Solution {
69public:
70    // Method to find the length of the Longest Increasing Subsequence (LIS)
71    // where the difference between adjacent elements is at most `k`.
72    int lengthOfLIS(vector<int>& nums, int k) {
73        int maxNum = *max_element(nums.begin(), nums.end());
74        SegmentTree* tree = new SegmentTree(maxNum);
75        int longest = 1;
76        for (int val : nums) {
77            // Get the LIS ending at val considering the constraint 'k'.
78            int localMax = tree->query(1, max(1, val - k), val - 1) + 1;
79            // Update the global LIS length.
80            longest = max(longest, localMax);
81            // Modify the segment tree to include the new LIS length for val.
82            tree->modify(1, val, localMax);
83        }
84        return longest;
85    }
86};
87

1// Represents a node in the segment tree with a value and range it covers.
2interface Node {
3    left: number;
4    right: number;
5    value: number;
6}
7
8// The segment tree is represented by an array of nodes.
9let tree: Node[] = [];
10
11// Push-up operation to update the parent node after modifications in the tree.
12function pushUp(index: number): void {
13    tree[index].value = Math.max(tree[index * 2].value, tree[index * 2 + 1].value);
14}
15
16// Builds the segment tree recursively.
17function build(index: number, left: number, right: number): void {
18    tree[index] = {left, right, value: 0};
19    if (left === right) return; // Base case: leaf node is reached.
20    let mid = Math.floor((left + right) / 2);
21    build(index * 2, left, mid);
22    build(index * 2 + 1, mid + 1, right);
23}
24
25// Modifies the value at a specific position in the segment tree.
26function modify(index: number, position: number, value: number): void {
27    if (tree[index].left === position && tree[index].right === position) {
28        tree[index].value = value;
29        return;
30    }
31    let mid = Math.floor((tree[index].left + tree[index].right) / 2);
32    if (position <= mid)
33        modify(index * 2, position, value);
34    else
35        modify(index * 2 + 1, position, value);
36    pushUp(index);
37}
38
39// Queries the maximum value within a range [left, right] in the segment tree.
40function query(index: number, left: number, right: number): number {
41    if (left <= tree[index].left && right >= tree[index].right) return tree[index].value;
42    let mid = Math.floor((tree[index].left + tree[index].right) / 2);
43    let maxValue = 0;
44    if (left <= mid) maxValue = query(index * 2, left, right);
45    if (right > mid) maxValue = Math.max(maxValue, query(index * 2 + 1, left, right));
46    return maxValue;
47}
48
49// Finds the length of the Longest Increasing Subsequence (LIS)
50// where the difference between adjacent elements is at most `k`.
51function lengthOfLIS(nums: number[], k: number): number {
52    let maxNum = Math.max(...nums);
53    // Initialize the segment tree with the size based on the maximum number in the array.
54    tree = new Array<Node>(4 * maxNum);
55    build(1, 1, maxNum);
56    let longest = 1;
57    for (let val of nums) {
58        // Get the longest subsequence length ending in `val` that respects the difference limit `k`.
59        let localMax = query(1, Math.max(1, val - k), val - 1) + 1;
60        // Update the result if the new LIS is longer.
61        longest = Math.max(longest, localMax);
62        // Update the segment tree with the new maximum LIS up to `val`.
63        modify(1, val, localMax);
64    }
65    return longest;
66}
67