查找最长的子序列的程序，在该子序列中，每个相邻元素之间的绝对差最大为k。
假设我们得到了一个数字列表和另一个值k。这次，我们的任务是找到最长子序列的长度，其中每个相邻元素之间的绝对差最大为k。
因此，如果输入类似于nums=[5、6、2、1，-6、0，-1，k=4，则输出将为6。
为了解决这个问题，我们将遵循以下步骤-
定义一个功能update()。这需要我，x
我：=我+n
当我不为零时，
segtree[i]：=segtree[i]的最大值，x
我：=我/2
定义一个功能query()。这需要我，j
ans：=-无穷大
我：=我+n
j：=j+n+1
当i<j为非零时
j：=j−1
ans：=ans的最大值，segtree[j]
ans：=ans的最大值，segtree[i]
我：=我+1
如果我的mod2与1相同
如果jmod2与1相同，则
我：=我/2
j：=j/2
返回ans
现在，在main函数中，执行以下操作-
nums=[5，6，2，1，-6，0，-1]
k=4
n=2的幂（对数（（数字的长度+1）+1）的对数以2为底
segtree：=[0]*100000
snums：=对列表中的nums进行排序
index：=进行收集，其中x：i为每个索引i和元素x中的（整数）
回答：=0
对于每个以num为单位的x
lo：=返回snums的最左边位置，可以在保持排序顺序的同时插入（x−k）
hi：=（snums的最左边位置，可以在保持排序顺序的同时插入（x+k））-1
数：=query(lo,hi)
更新（索引[x]，计数+1）
ans：=ans的最大值，计数+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))输入值
[5, 6, 2, 1, −6, 0, −1], 4输出结果
6