Chương trình tìm độ dài dãy con xen kẽ bất đẳng thức dài nhất trong Python

Giả sử chúng ta có một danh sách các số gọi là nums, và cần tìm độ dài của dãy con dài nhất trong nums sao cho mối quan hệ bất đẳng thức giữa mọi hai số liên tiếp thay đổi xen kẽ giữa phép nhỏ hơn và lớn hơn. Hai số đầu tiên có thể là quan hệ nhỏ hơn hoặc lớn hơn.

Ví dụ, nếu đầu vào là nums = [1, 2, 6, 4, 5], thì kết quả sẽ là 4, vì dãy con xen kẽ bất đẳng thức dài nhất là [2, 6, 4, 5] với 2 < 6 > 4 < 5.

Giải thuật

Để giải bài toán này, chúng ta thực hiện các bước sau:

1. Định nghĩa hàm get_direction(a, b):
   • Trả về 0 nếu a == b
   • Trả về -1 nếu a < b
   • Trả về 1 nếu a > b
2. Nếu độ dài của nums nhỏ hơn 2, trả về độ dài của nums.
3. Khởi tạo: max_length = 1, cur_length = 1, last_direction = 0.
4. Duyệt qua mảng từ i = 0 đến len(nums) - 2:
   • Tính direction = get_direction(nums[i], nums[i + 1]).
   • Nếu direction == 0 (hai số bằng nhau): đặt cur_length = 1.
   • Ngược lại, nếu direction == last_direction (hướng không đổi): đặt cur_length = 2.
   • Ngược lại (hướng thay đổi): tăng cur_length lên 1.
   • Cập nhật max_length = max(max_length, cur_length).
   • Cập nhật last_direction = direction.
5. Trả về max_length.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        if len(nums) < 2:
            return len(nums)
        
        def get_direction(a, b):
            return 0 if a == b else -1 if a < b else 1
        
        max_length = 1
        cur_length = 1
        last_direction = 0
        
        for i in range(len(nums) - 1):
            direction = get_direction(nums[i], nums[i + 1])
            if direction == 0:
                cur_length = 1
            elif direction == last_direction:
                cur_length = 2
            else:
                cur_length += 1
            max_length = max(max_length, cur_length)
            last_direction = direction
        
        return max_length

ob = Solution()
nums = [1, 2, 6, 4, 5]
print(ob.solve(nums))  # Output: 4

Đầu vào

[1, 2, 6, 4, 5]

Đầu ra

4