Pythonで隣接するすべての要素間の絶対差が最大で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：=−infinity

• 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を返す

• ここで、main関数で、次のようにします-

• nums =[5、6、2、1、-6、0、-1]

• k =4

• n =2の2乗（（長さ（nums）+ 1）+ 1）の2を底とする対数

• segtree：=[0] * 100000

• snums：=リスト番号を並べ替える

• index：=（snums）の各インデックスiと要素xのx：iであるコレクションを作成します

• ans：=0

• numsのxごとに、実行します

  • lo：=snumsから左端の位置を返します。ここで、（x − k）は、ソートされた順序を維持しながら挿入できます

  • hi：=（snumsの左端の位置。ここで、（x + k）は、ソートされた順序を維持しながら挿入できます）− 1

  • count：=query（lo、hi）

  • update（index [x]、count + 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