2407. Longest Increasing Subsequence II

Problem Link

Description

---

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.

 

Example 1:

Input: nums = [4,2,1,4,3,4,5,8,15], k = 3
Output: 5
Explanation:
The longest subsequence that meets the requirements is [1,3,4,5,8].
The subsequence has a length of 5, so we return 5.
Note that the subsequence [1,3,4,5,8,15] does not meet the requirements because 15 - 8 = 7 is larger than 3.

Example 2:

Input: nums = [7,4,5,1,8,12,4,7], k = 5
Output: 4
Explanation:
The longest subsequence that meets the requirements is [4,5,8,12].
The subsequence has a length of 4, so we return 4.

Example 3:

Input: nums = [1,5], k = 1
Output: 1
Explanation:
The longest subsequence that meets the requirements is [1].
The subsequence has a length of 1, so we return 1.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 105

Solution

---

Python3

class SegmentTree:
    # https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
 
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])
 
    def __delitem__(self, idx):
        self[idx] = self._default
 
    def __getitem__(self, idx):
        return self.data[idx + self._size]
 
    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(
                self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1
 
    def __len__(self):
        return self._len
 
    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size
 
        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1
 
        return self._func(res_left, res_right)
 
    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
 
class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        N = len(nums)
        m = max(nums)
        st = SegmentTree([0] * (m + 1))
        res = 1
        
        for x in nums:
            left, right = max(1, x - k), x
            q = st.query(left, right)
            st[x] = 1 + q
            if st[x] > res:
                res = st[x]
 
        return res