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

मान लीजिए हमारे पास एक ऐरे nums है, और एक और ऐरे requests है जहां requests[i] = [start_i, end_i], यह iवें अनुरोध को दर्शाता है जो nums[start_i] + nums[start_i+1] + ... + nums[end_i] के योग के लिए पूछता है। हमें nums के सभी क्रमचयों के बीच सभी अनुरोधों का अधिकतम कुल योग ढूंढना है। उत्तर बहुत बड़ा हो सकता है, इसलिए इसे मॉड्यूलो 10^9+7 वापस करें।

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

समाधान के चरण

1. A := []
2. requests में प्रत्येक अनुरोध (s, e) के लिए:
   • A.append((s, 0))
   • A.append((e, 1))
3. A सूची को सॉर्ट करें
4. fr := defaultdict(list)
5. cnt := 0
6. n := len(A)
7. i := 0
8. while i < n:
   • r := 1
   • while i < n-1 and A[i+1] == A[i]:
     • r += 1
     • i += 1
   • p, flag = A[i]
   • यदि flag == 0:
     • cnt += r
     • यदि cnt - r > 0:
       • fr[cnt-r].append((pre, p-1))
       • pre := p
   • अन्यथा जब flag == 1:
     • cnt -= r
     • fr[cnt+r].append((pre, p))
     • pre := p+1
   • i += 1
9. nums को रिवर्स ऑर्डर में सॉर्ट करें
10. ks := sorted(fr.keys(), reverse=True)
11. ans := 0
12. m := 10**9 + 7
13. i := 0
14. ks में प्रत्येक k के लिए:
    • fr[k] में प्रत्येक जोड़ी (s, e) के लिए:
      • d := e - s + 1
      • ans += sum(nums[i:i+d]) * k
      • ans %= m
      • i += d
15. ans वापस करें

उदाहरण

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

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 = sorted(fr.keys(), 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