2407. Longest Increasing Subsequence II

You are given an integer array nums and an integer k.

Find the longest subsequence of nums that meets the following requirements:

• The subsequence is strictly increasing and
• The difference between adjacent elements in the subsequence is at most k.

Return the length of the longest subsequence that meets the requirements.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

c++

struct Seg {
    int mi, ma, n;
    Seg *left, *right;
    
    Seg(vector<int>& A, int l, int r) : mi(A[l]), ma(A[r]), n(0), left(nullptr), right(nullptr) {
        if(l != r) {
            int m = l + (r - l) / 2;
            left = new Seg(A, l, m);
            right = new Seg(A, m + 1, r);
        }
    }
    
    void update(int k, int v) {
        if(mi <= k and k <= ma) {
            n = max(n,v);
            if(left) left->update(k,v);
            if(right) right->update(k,v);
        }
    }
    
    int query(int l, int r) {
        if(l <= mi and ma <= r) return n;
        if(r < mi or ma < l) return 0;
        return max((left ? left->query(l,r) : 0), (right ? right->query(l,r) : 0));
    }
};
class Solution {
public:
    int lengthOfLIS(vector<int>& A, int k) {
        int n = A.size(), res = 1;
        vector<int> S = A;
        sort(begin(S), end(S));
        S.erase(unique(begin(S), end(S)), end(S));
        Seg* seg = new Seg(S, 0, S.size() - 1);
        for(int i = n - 1; i >= 0; i--) {
            int now = 1 + seg->query(A[i] + 1, A[i] + k);
            res = max(res, now);
            seg->update(A[i], now);
        }
        return res;
    }
};