পাইথনে m দ্বারা সাবয়ারের মডিউলের সর্বাধিক যোগফল খুঁজে বের করার প্রোগ্রাম

Python

ধরুন আমাদের 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 + x এর শেষ আইটেম) csum এর শেষে mod m
• দেখা হয়েছে :=একক উপাদান সহ একটি তালিকা যা প্রাথমিকভাবে 0
• সর্বোচ্চ_সমষ্টি :=-1
• csum-এ প্রতিটি s-এর জন্য, করুন
  • idx :=বাম অবস্থানে s ঢোকাতে দেখা গেছে যাতে তালিকাটি সাজানো হয়
  • যদি idx <সাইজ দেখা যায়, তাহলে
    • max_sum :=সর্বাধিক_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)]

আউটপুট

3