Chương trình tìm độ dài dãy con dài nhất có tốc độ không đổi của xe bằng Python

Cho danh sách vị trí xe tại các khoảng thời gian đều nhau. Tìm độ dài dãy con liên tiếp dài nhất mà xe chuyển động với tốc độ không đổi.

Ví dụ: positions = [0,4,8,12,6,4,0] → 4 (dãy [0,4,8,12]).

Giải thuật

• Duyệt mảng, giữ khoảng cách distance giữa hai vị trí liên tiếp hiện tại.
• Nếu khoảng cách mới bằng distance → tăng độ dài dãy hiện tại.
• Khác → cập nhật max, reset độ dài hiện tại = 1, cập nhật distance mới.
• Trả về max_cnt + 1 (số phần tử = số khoảng cách + 1).

Ví dụ minh họa

class Solution:
    def solve(self, positions):
        j = 1
        max_cnt = 0
        current = 0
        distance = abs(positions[0] - positions[1])
        while j < len(positions):
            prev = positions[j-1]
            if distance == abs(positions[j] - prev):
                current += 1
            else:
                max_cnt = max(max_cnt, current)
                current = 1
                distance = abs(positions[j] - prev)
            max_cnt = max(max_cnt, current)
            j += 1
        return max_cnt + 1

ob = Solution()
positions = [0, 4, 8, 12, 6, 4, 0]
print(ob.solve(positions))

Đầu vào

[0, 4, 8, 12, 6, 4, 0]

Đầu ra

4