Python에서 모든 순열의 최대 합을 찾는 프로그램

nums 배열이 있고 requests[i] =[start_i, end_i]인 요청이라는 다른 배열이 있다고 가정합니다. 이는 i번째 요청이 nums[start_i] + nums[start_i+1] + ... + 숫자[end_i-1] + 숫자[end_i]. num의 모든 순열 중에서 모든 요청의 최대 합계를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9+7을 반환합니다.

따라서 입력이 nums =[10,20,30,40,50] requests =[[1,3],[0,1]]과 같으면 출력은 190이 됩니다. ,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 :=새 목록
• 요청의 각 요청(들, e)에 대해 다음을 수행합니다.
  • A 끝에 쌍(s, 0) 삽입
  • A 끝에 쌍(e, 1) 삽입
• 목록 A 정렬
• fr :=빈 지도
• cnt :=0
• n :=A의 크기
• i :=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