用于查找 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。
示例
让我们看看以下实现以获得更好的理解-
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