Chương trình tìm độ dài dãy con xen kẽ dấu dài nhất trong Python

Mô tả bài toán

Cho danh sách nums. Tìm độ dài dãy con (không nhất thiết liên tiếp) dài nhất mà dấu của các số xen kẽ nhau (dương/âm).

Ví dụ: nums = [1, 3, -6, 4, -3] → đầu ra 4 (dãy con [1, -6, 4, -3]).

Giải thuật (DP O(1) space)

1. Khởi tạo pos = 0 (độ dài dãy kết thúc bằng số dương), neg = 0 (kết thúc bằng số âm).
2. Duyệt qua từng n:
   • Nếu n < 0: neg = pos + 1.
   • Ngược lại: pos = neg + 1.
3. Trả về max(pos, neg).

Ví dụ mã Python

class Solution:
    def solve(self, nums):
        pos = neg = 0
        for n in nums:
            if n < 0:
                neg = pos + 1
            else:
                pos = neg + 1
        return max(pos, neg)

ob = Solution()
nums = [1, 3, -6, 4, -3]
print(ob.solve(nums))

Đầu vào

[1, 3, -6, 4, -3]

Đầu ra

4