โปรแกรมหาผลรวม Subarray Modulo M สูงสุดใน Python

ให้ Array nums และ m หา max(subarray_sum % m)

ตัวอย่าง: nums=[1,5,7,3], m=5 → 3

ขั้นตอน (Prefix Sum + Ordered Set)

1. คำนวณ Prefix Sum Modulo m → csum
2. Maintain Sorted List seen ของ Prefix ที่ผ่านมา
3. สำหรับแต่ละ s ใน csum: หา seen[idx] > s แรก (Bisect) → Candidate = (s - seen[idx]) % m
4. Update Max

ตัวอย่างโค้ด

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))  # Output: 3

อินพุต

[1,5,7,3], 5

เอาต์พุต

3