Pythonの順列から得られる最大合計を見つけるプログラム

配列numsがあり、requests [i] =[start_i、end_i]であるrequestsという別の配列があるとします。これは、i番目の要求がnums [start_i] + nums [start_i + 1] +...+の合計を要求することを表します。 nums [end_i-1] +nums[end_i]。 numのすべての順列の中から、すべての要求の最大合計を見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法として返します。

したがって、入力がnums =[10,20,30,40,50]リクエスト=[[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
• 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