Chương trình tìm độ dài dãy con dài nhất có tổng bằng 0 trong Python

Giả sử chúng ta có một danh sách chỉ chứa hai giá trị 1 và -1. Nhiệm vụ là tìm độ dài của dãy con (sublist) dài nhất mà tổng các phần tử bằng 0.

Ví dụ: với đầu vào nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1], kết quả là 8, vì dãy con dài nhất là [-1, 1, 1, -1, 1, -1, 1, -1] có tổng bằng 0.

Giải thuật

Chúng ta sử dụng kỹ thuật tiền tố cộng (prefix sum) kết hợp với bảng băm (hash map) để lưu trữ chỉ số đầu tiên xuất hiện của mỗi giá trị tổng tiền tố.

• Khởi tạo table là một từ điển rỗng, cs = 0 (tổng tiền tố hiện tại), max_diff = 0 (độ dài lớn nhất).
• Duyệt qua mảng với chỉ số i từ 0 đến len(nums)-1:
  • Cập nhật cs += nums[i].
  • Nếu cs == 0, cập nhật max_diff = max(max_diff, i + 1).
  • Nếu cs đã có trong table, cập nhật max_diff = max(max_diff, i - table[cs]).
  • Ngược lại, lưu table[cs] = i (chỉ lưu lần đầu xuất hiện).
• Trả về max_diff.

Mã nguồn Python

class Solution:
    def solve(self, nums):
        table = {}
        cs = 0
        max_diff = 0
        for i in range(len(nums)):
            cs += nums[i]
            if cs == 0:
                max_diff = max(i + 1, max_diff)
            if cs in table:
                max_diff = max(max_diff, i - table[cs])
            else:
                table[cs] = i
        return max_diff

ob = Solution()
nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]
print(ob.solve(nums))  # Output: 8

Đầu vào

[1, 1, -1, 1, 1, -1, 1, -1, 1, -1]

Đầu ra

8