पायथन में किसी भी क्रमपरिवर्तन से प्राप्त अधिकतम योग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक सरणी संख्या है, और एक अन्य सरणी अनुरोध कहा जाता है जहां अनुरोध [i] =[start_i, end_i], यह ith अनुरोध का प्रतिनिधित्व करता है जो अंकों के योग के लिए पूछता है [start_i] + अंक [start_i + 1] + ... + अंक [end_i-1] + अंक [end_i]। हमें अंकों के सभी क्रमपरिवर्तनों के बीच सभी अनुरोधों का अधिकतम कुल योग ज्ञात करना है। उत्तर बहुत बड़ा हो सकता है, इसलिए इसे मॉड्यूलो 10^9+7 लौटाएं।

इसलिए, यदि इनपुट अंकों की तरह है =[10,20,30,40,50] अनुरोध =[[1,3], [0,1]], तो आउटपुट 190 होगा, क्योंकि अगर हम [30] की तरह व्यवस्था करते हैं ,50,40,20,10] हम प्राप्त करते हैं:अनुरोधों से [0]:अंक [1] + अंक [2] + अंक [3] =50 + 40 + 20 =110, और अनुरोधों से [1]:अंक [ 0] + अंक [1] =30 + 50 =80, तो कुल योग 110+80 =190।

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

• A :=एक नई सूची
• अनुरोधों में प्रत्येक अनुरोध (एस, ई) के लिए, करें
  • ए के अंत में जोड़ी (ओं, 0) डालें
  • ए के अंत में जोड़ी (ई, 1) डालें
• सूची A को क्रमित करें
• fr :=एक खाली नक्शा
• सीएनटी:=0
• n :=A का आकार
• मैं :=0
• जबकि मैं
• r :=1
• जबकि i
• r :=r + 1
• i :=i + 1

उदाहरण

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

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