查找最长的子序列的程序，在该子序列中，每个相邻元素之间的绝对差最大为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
如果我的mod 2与1相同
如果j mod 2与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, bisectclass 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
以上是 查找最长的子序列的程序，在该子序列中，每个相邻元素之间的绝对差最大为k。 的全部内容， 来源链接： utcz.com/z/315921.html
