Chương trình tìm tổng lớn nhất của mảng con modulo m trong Python

Cho mảng nums và số m. Tìm giá trị lớn nhất của (tổng mảng con) mod m.

Ví dụ: , → kết quả .

Thuật toán giải quyết (Prefix Sum + Cây BST / Sorted List O(n log n))

1. Tính mảng tiền tố modulo:
2. Duy trì danh sách đã sắp xếp các giá trị đã gặp (khởi tạo )
3. Với mỗi trong :
   • Tìm chỉ số chèn
   • Nếu : 후보 =
   • Ngược lại: ứng viên =
   • Cập nhật
   • Chèn vào giữ thứ tự
4. Trả về

Ý tưởng: (sum[j] - sum[i]) % m = (csum[j] - csum[i]) % m. Muốn lớn nhất → tìm csum[i] nhỏ nhất > csum[j].

Ví dụ minh họa

import bisect

def solve(nums, m):
    csum = [nums[0] % m]
    for x in nums[1:]:
        csum.append((csum[-1] + x) % m)
    seen = [0]
    max_sum = -1
    for s in csum:
        idx = bisect.bisect_left(seen, s)
        if idx < len(seen):
            max_sum = max(max_sum, s, (s - seen[idx]) % m)
        else:
            max_sum = max(max_sum, s)
        bisect.insort_left(seen, s)
    return max_sum

nums = [1, 5, 7, 3]
m = 5
print(solve(nums, m))

Đầu vào

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

Đầu ra

3