Chương trình tìm độ dài dãy con luân phiên dài nhất trong Python

Cho danh sách số nums, tìm độ dài dãy con dài nhất mà hiệu giữa các phần tử liên tiếp luân phiên đổi dấu (dương, âm, dương... hoặc âm, dương, âm...).

Ví dụ: nums = [6, 10, 4, 2, 3, 9, 4, 7] → dãy con [6, 10, 2, 9, 4, 7] có hiệu [4, -8, 7, -5, 3] luân phiên, độ dài 6.

Giải thuật (DP 2 trạng thái)

• dp[i][0]: độ dài dãy con kết thúc tại i với hiệu cuối cùng > 0 (tăng).
• dp[i][1]: độ dài dãy con kết thúc tại i với hiệu cuối cùng < 0 (giảm).
• Khởi tạo dp[i][*] = 1.
• Duyệt i từ 0 đến n-1, j từ 0 đến i-1:
  • Nếu nums[j] < nums[i]: dp[i][0] = max(dp[i][0], dp[j][1] + 1).
  • Nếu nums[j] > nums[i]: dp[i][1] = max(dp[i][1], dp[j][0] + 1).
• Kết quả là max của tất cả dp[i][0] và dp[i][1].

Mã nguồn 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))  # Output: 6

Đầu vào

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

Đầu ra

6