পাইথনে যেকোন স্থানচ্যুতি থেকে প্রাপ্ত সর্বাধিক যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে সংখ্যা আছে, এবং আরেকটি অ্যারে যাকে অনুরোধ বলা হয় যেখানে অনুরোধ [i] =[start_i, end_i], এটি ith অনুরোধটি nums[start_i] + nums[start_i+1] + ... + এর যোগফলের জন্য অনুরোধ করে। সংখ্যা[end_i-1] + nums[end_i]। আমাদের সংখ্যার সমস্ত অনুক্রমের মধ্যে সমস্ত অনুরোধের সর্বাধিক মোট যোগফল খুঁজে বের করতে হবে। উত্তরটি অনেক বড় হতে পারে, তাই এটি মডিউল 10^9+7 ফেরত দিন।

সুতরাং, ইনপুট যদি সংখ্যার মত হয় =[10,20,30,40,50] অনুরোধ =[[1,3],[0,1]], তাহলে আউটপুট হবে 190, কারণ যদি আমরা [30] এর মতো সাজাই। ,50,40,20,10] আমরা পাই:অনুরোধ থেকে[0] :nums[1] + nums[2] + nums[3] =50 + 40 + 20 =110, এবং অনুরোধ থেকে[1] :nums[ 0] + সংখ্যা[1] =30 + 50 =80, তাই মোট যোগফল 110+80 =190।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

• A :=একটি নতুন তালিকা
• প্রতিটি অনুরোধের (s, e) অনুরোধের জন্য, করুন
  • A-এর শেষে জোড়া (s, 0) ঢোকান
  • A-এর শেষে জোড়া (e, 1) ঢোকান
• তালিকা A সাজান
• fr :=একটি খালি মানচিত্র
• cnt :=0
• n :=A এর আকার
• i :=0
• যখন i
• r :=1
• যখন i
• r :=r + 1
• i :=i + 1

করুন
• fr[k] তে প্রতিটি জোড়ার (s, e) জন্য, করুন
  • d :=e - s + 1
  • উত্তর :=উত্তর + (সংখ্যার সমস্ত উপাদানের যোগফল[সূচি i থেকে i+d-1]) * k
  • উত্তর :=ans mod m
  • i :=i + d

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from collections import defaultdict
def solve(nums, requests):
   A = []
   for s, e in requests:
      A.append((s, 0))
      A.append((e, 1))
   A.sort()
   fr = defaultdict(list)
   cnt = 0

   n = len(A)
   i = 0
   while i < n:
      r = 1
      while i < n - 1 and A[i+1] == A[i]:
         r += 1
         i += 1
      p, flag = A[i]
      if flag == 0:
         cnt += r
         if cnt - r > 0:
            fr[cnt-r].append((pre, p-1))
         pre = p
      elif flag == 1:
         cnt -= r
         fr[cnt+r].append((pre, p))
         pre = p+1
      i += 1

   nums.sort(reverse=True)
   ks = list(fr.keys())
   ks.sort(reverse=True)
   ans = 0
   m = 10**9 + 7
   i = 0
   for k in ks:
      for s, e in fr[k]:
         d = e - s + 1
         ans += sum(nums[i:i+d]) * k
         ans %= m
         i += d
   return ans

nums = [10,20,30,40,50]
requests = [[1,3],[0,1]]
print(solve(nums, requests))

ইনপুট

[10,20,30,40,50],[[1,3],[0,1]]

আউটপুট

190