在Python中查找任何排列中所得到的最大总和的程序

假设我们有一个数组nums和另一个名为requests的数组，其中requests[i] = [start_i，end_i]，表示第i个请求要求nums[start_i]+nums[start_i+1]+…+nums[end_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。

要解决此问题，我们将遵循以下步骤：

A：一个新列表
对于请求中的每个(s，e)，执行以下操作
- 在A的末尾插入对(s，0)
- 在A的末尾插入对(e，1)
对列表A进行排序
fr：一个空映射
cnt：0
n：A的大小
i：0
当i < n时，执行以下操作
- r：1
- 当i < n-1并且A [i + 1]与A [i]相同时，执行以下操作
  - r：r + 1
  - i：i + 1
- cnt：cnt + r
- 当cnt – r> 0时，执行以下操作
  - 在fr [cnt-r]的末尾插入(pre，p-1)
  - pre：p
- 否则，当flag等于1时，执行以下操作
  - cnt：cnt-r
  - 在fr [cnt + r]的末尾插入(pre，p)
  - pre：p + 1
- i：i + 1
对nums列表按逆序进行排序
ks：一个由fr的所有键列表组成的新列表
对列表ks按逆序进行排序
ans：0
m：10 ^ 9 + 7
i：0
对于ks中的每个k，请执行以下操作
- 对于fr [k]中的每个对(s，e)，执行以下操作
  - d：e-s +1
  - ans：ans +（nums [从索引i到i + d-1的所有元素的总和]）* k
  - ans：ans模m
  - i：i + d
返回ans

例

请看以下实现，以便更好地理解−

from collections importdefaultdict
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))