Pythonの特定のリストから最長の交互サブシーケンスの長さを見つけるプログラム

numsと呼ばれる数値のリストがあるとすると、2つの連続する数値の差が正と負の間で交互になる、最長のサブシーケンスのサイズを見つける必要があります。そして、最初の違いは正または負のいずれかです。

したがって、入力がnums =[6、10、4、2、3、9、4、7]のような場合、必要なサブシーケンスは[6、10、2、9、4]であるため、出力は6になります。 、7]であり、違いは[4、-8、7、-5、3]です。

これを解決するために、次の手順に従います＆minuS;

• n：=numsのサイズ
• dp：=サイズ2nのリストで、1で埋めます
• ans：=0
• 0からnの範囲のiについては、
  • 0からiの範囲のjについては、
    • nums [j]
    • dp [i、0] =dp [i、0]および（dp [j、1] + 1）の最大値
  • それ以外の場合、nums [j]> nums [i]の場合、
    • dp [i、1] =dp [i、1]および（dp [j、0] + 1）の最大値
• ans =ansの最大値、dp [i、0]およびdp [i、1]）

例（Python）

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, nums):
      n = len(nums)
      dp = [[1] * 2 for _ in range(n)]
      ans = 0
      for i in range(n):
         for j in range(i):
            if nums[j] < nums[i]:
               dp[i][0] = max(dp[i][0], dp[j][1] + 1)
            elif nums[j] > nums[i]:
               dp[i][1] = max(dp[i][1], dp[j][0] + 1)
         ans = max(ans, dp[i][0], dp[i][1])
      return ans
ob = Solution()
nums = [6, 10, 4, 2, 3, 9, 4, 7]
print(ob.solve(nums))

入力

[6, 10, 4, 2, 3, 9, 4, 7]

出力

6