Chương trình tìm độ dài của dãy con xen kẽ dài nhất từ ​​một danh sách nhất định bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải tìm kích thước của dãy con dài nhất mà hiệu giữa hai số liên tiếp xen kẽ giữa số dương và số âm. Và sự khác biệt đầu tiên có thể là tích cực hoặc tiêu cực.

Vì vậy, nếu đầu vào giống như nums =[6, 10, 4, 2, 3, 9, 4, 7], thì đầu ra sẽ là 6, vì có thể dãy con bắt buộc là [6, 10, 2, 9, 4 , 7] và sự khác biệt là [4, -8, 7, -5, 3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau &minuS;

• n:=kích thước của nums
• dp:=một danh sách có kích thước 2n và điền bằng 1
• ans:=0
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • đối với j trong phạm vi 0 đến i, thực hiện
    • nếu nums [j]
    • dp [i, 0] =tối đa là dp [i, 0] và (dp [j, 1] + 1)
  • ngược lại khi nums [j]> nums [i], thì
    • dp [i, 1] =tối đa là dp [i, 1] và (dp [j, 0] + 1)
• ans =tối đa ans, dp [i, 0] và dp [i, 1])

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

6