पायथन में सबअरे के अधिकतम योग को m से मोड्यूलो करके ढूंढना

पायथन में सबअरे के अधिकतम योग को m से मोड्यूलो करके ढूंढना।

मान लीजिए हमारे पास n तत्वों की एक ऐरे nums है। हमारे पास एक और इंटीजर m है। हमें इसके किसी भी सबअरे के योग के अधिकतम मान को m से मोड्यूलो करके ढूंढना है।

उदाहरण के लिए, यदि इनपुट है nums = [1,5,7,3], m = 5, तो आउटपुट होगा 3 क्योंकि:

[1] mod 5 = 1
[5] mod 5 = 0
[7] mod 5 = 2
[3] mod 5 = 3
[1,5] mod 5 = 1
[5,7] mod 5 = 2
[7,3] mod 5 = 0
[1,5,7] mod 5 = 3
[5,7,3] mod 5 = 0
[1,5,7,3] mod 5 = 1

समाधान दृष्टिकोण

प्रीफिक्स सम मोड्यूलो m का उपयोग करें। प्रत्येक प्रीफिक्स सम s के लिए, हमें सबसे छोटा पिछला प्रीफिक्स सम ढूंढना है जो s से बड़ा है (ताकि (s - prev) % m अधिकतम हो)। सॉर्टेड कंटेनर के लिए bisect का उपयोग करें।

csum में प्रीफिक्स सम मोड्यूलो m की गणना करें।
seen = [0] (सॉर्टेड पिछले प्रीफिक्स सम) आरंभ करें।
प्रत्येक s के लिए csum में:
- idx = bisect_left(seen, s) ढूंढें।
- यदि idx < len(seen), तो max_sum = max(max_sum, s, (s - seen[idx]) % m) अपडेट करें।
- अन्यथा max_sum = max(max_sum, s)।
- insort_left(seen, s)।
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))

इनपुट

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