โปรแกรมหาผลรวมสูงสุดที่ได้จากการเรียงสับเปลี่ยนใน Python

สมมติว่าเรามีอาร์เรย์จำนวนหนึ่งและอาร์เรย์อื่นที่เรียกว่าการร้องขอโดยที่การร้องขอ[i] =[start_i, end_i] นี่หมายถึงคำขอ ith ขอผลรวมของ nums[start_i] + nums[start_i+1] + ... + nums[end_i-1] + ตัวเลข[end_i] เราต้องหาผลรวมสูงสุดของคำขอทั้งหมดจากการเรียงสับเปลี่ยนของ nums ทั้งหมด คำตอบอาจมีขนาดใหญ่มาก ให้คืนค่าเป็นโมดูล 10^9+7

ดังนั้นหากอินพุตเป็น nums =[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] + nums[1] =30 + 50 =80 ดังนั้นผลรวมทั้งหมด 110+80 =190

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• A :=รายการใหม่
• สำหรับแต่ละคำขอ (s, e) ในคำขอ ให้ทำ
  • ใส่คู่ (s, 0) ที่ส่วนท้ายของ A
  • ใส่คู่ (e, 1) ที่ส่วนท้ายของ A
• เรียงลำดับรายการ A
• fr :=แผนที่ว่างเปล่า
• cnt :=0
• n :=ขนาดของ A
• ผม :=0
• ในขณะที่ฉัน
• r :=1
• ในขณะที่ i
• r :=r + 1
• ผม :=ผม + 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