查找最长的子序列的程序,在该子序列中,每个相邻元素之间的绝对差最大为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