पायथन में मी द्वारा सबएरे मॉड्यूलो का अधिकतम योग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी संख्या है। हमारे पास एक और पूर्णांक m है। हमें इसके किसी भी उप-सरणी मॉड्यूल एम के योग का अधिकतम मान ज्ञात करना है।

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

[1] मॉड 5 =1
[5] मॉड 5 =0
[7] मॉड 5 =2
[3] मॉड 5 =3
[1,5] मॉड 5 =1
[5,7] मॉड 5 =2
[7,3] मॉड 5 =0
[1,5,7] मॉड 5 =3
[5,7,3] मॉड 5 =0
[1,5,7,3] मॉड 5 =1

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

csum :=एक सूची और शुरू में इसमें nums[0] mod m डालें
पहले मान को छोड़कर प्रत्येक x के लिए अंकों में, करें
- csum के अंत में (csum + x का अंतिम आइटम) mod m डालें
देखा:=एक सूची जिसमें शुरुआत में एकल तत्व है जो कि 0 है
अधिकतम_योग:=-1
csum में प्रत्येक s के लिए, करें
- idx :=s को सीन में डालने के लिए सबसे बाईं ओर की स्थिति ताकि सूची को क्रमबद्ध किया जा सके
- यदि idx <देखा का आकार, तो
  - max_sum :=max_sum और s का अधिकतम
- अन्यथा,
  - देखे गए सबसे बाईं ओर के इंडेक्स में s डालें ताकि ऐरे को सॉर्ट किया जा सके
- देखे गए सबसे बाईं ओर के इंडेक्स में s डालें ताकि ऐरे को सॉर्ट किया जा सके
अधिकतम_योग लौटाएं

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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)]