Python程式：查詢給定列表中最長交替子序列的長度

假設我們有一個名為nums的數字列表，我們需要找到最長子序列的長度，其中兩個連續數字之間的差在正數和負數之間交替。第一個差可以是正數或負數。

因此，如果輸入類似於nums = [6, 10, 4, 2, 3, 9, 4, 7]，則輸出將為6，因為可能的所需子序列是[6, 10, 2, 9, 4, 7]，而差值為[4, -8, 7, -5, 3]。

為了解決這個問題，我們將遵循以下步驟：

• n := nums的長度
• dp := 長度為2n的列表，並填充為1
• ans := 0
• 對於範圍從0到n的i：
  • 對於範圍從0到i的j：
    • 如果nums[j] < nums[i]，則
      • 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]的最大值
• 返回ans

示例 (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

Arnab Chakraborty

更新於：2020年12月12日

瀏覽量：395

開啟您的職業生涯

完成課程獲得認證

開始學習