Python程序 – 查找最长子序列，其中每个相邻元素的绝对差不大于k。

假设我们有一个数字列表和一个值k。这一次，我们的任务是找到最长子序列的长度，其中每个相邻元素的绝对差不大于k。

因此，如果输入是nums = [5, 6, 2, 1, −6, 0, −1， k = 4，则输出将为6。

为了解决这个问题，我们将遵循以下步骤−

定义一个函数update()。这会获取i，x
i：= i + n
如果i非零，请执行以下操作
- segtree [i]：= segtree [i]，x中的最大值
- i：= i / 2
定义一个函数query()。这会取i，j
ans：= -无限大
i：= i + n
j：= j + n + 1
如果i
- 如果i mod 2与1相同，则
  - ans：= ans，segtree [i]的最大值
  - i：= i + 1
- 如果j mod 2与1相同，则
  - j：= j−1
  - ans：= ans，segtree [j]的最大值
- i：= i / 2
- j：= j / 2
返回ans
现在，在主要函数中，执行以下操作−
nums = [5, 6, 2, 1, −6, 0, −1]
k = 4
n = 2的幂（对（nums）的长度的对数2 + 1的对数）
segtree = [0] * 100,000
snums =对列表nums进行排序
index =创建一个集合，其中x：i，对于（snums）中的每个索引i和元素x
ans = 0
对于nums中的每个x，执行以下操作
- 返回从snums的最左侧位置开始，可以插入（x-k），同时保持排序顺序
- hi = （从snums的最左侧位置开始，可以插入（x + k），同时保持排序顺序）- 1
- count = query（lo，hi）
- update（index [x]，count + 1）
- ans = max（ans，count + 1）
返回ans

以下是具体实现代码，仅供参考：

import math, bisect
class Solution:
   def solve(self, nums, k):
      n = 2 ** int(math.log2(len(nums) + 1) + 1)
      segtree = [0] * 100000
      def update(i, x):
         i += n
         while i:
            segtree[i] = max(segtree[i], x)
            i //= 2
      def query(i, j):
         ans = −float("inf")
         i += n
         j += n + 1
         while i < j:
            if i % 2 == 1:
               ans = max(ans, segtree[i])
               i += 1
            if j % 2 == 1:
               j −= 1
               ans = max(ans, segtree[j])
            i //= 2
            j //= 2
         return ans
      snums = sorted(nums)
      index = {x: i for i, x in enumerate(snums)}
      ans = 0
      for x in nums:
         lo = bisect.bisect_left(snums, x − k)
         hi = bisect.bisect_right(snums, x + k) − 1
         count = query(lo, hi)
         update(index[x], count + 1)
         ans = max(ans, count + 1)
      return ans
ob = Solution()
print(ob.solve([5, 6, 2, 1, −6, 0, −1], 4))