পাইথনে সাবঅ্যারে যোগফলের মডুলো m-এর সর্বোচ্চ মান বের করার প্রোগ্রাম

একটি অ্যারে nums এবং ইন্টিজার m দেওয়া আছে। যেকোনো সাবঅ্যারের যোগফল মডুলো m-এর সর্বোচ্চ মান বের করুন।

উদাহরণ

nums = [1,5,7,3], m = 5 → আউটপুট: 3

এলগরিদম (প্রিফিক্স সাম + বাইনারি সার্চ)

1. csum[0] = nums[0] % m
2. for x in nums[1:]: csum.append((csum[-1]+x) % m)
3. seen := [0] (সোর্টেড লিস্ট)
4. প্রতিটি s ইন csum:
   • idx := bisect_left(seen, s)
   • যদি idx < len(seen): max_sum = max(max_sum, s, (s - seen[idx]) % m)
   • insort_left(seen, s)
5. max_sum রিটার্ন করুন।

পাইথন কোড

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))  # আউটপুট: 3

ইনপুট / আউটপুট

[1,5,7,3], 5
3