n개의 양수 요소가 있는 배열 num이 있다고 가정합니다. 비어 있지 않은 모든 연속 하위 배열의 합을 계산한 다음 n*(n+1)/2 숫자의 새 배열을 만들어 감소하지 않는 방식으로 정렬합니다. 새 배열에서 왼쪽 인덱스에서 오른쪽 인덱스(1-인덱스)까지의 숫자 합계를 찾아야 합니다. 답은 매우 클 수 있으므로 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 nums =[1,5,2,6] left =1 right =5와 같으면 출력은 20이 됩니다. 여기서 모든 하위 배열 합계는 1, 5, 2, 6, 6, 7, 8이기 때문입니다. , 8, 13, 14, 그래서 정렬 후 [1,2,5,6,6,7,8,8,13,14], 인덱스 1에서 5까지 요소의 합은 1+5+2 +6+6 =20.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=10^9 + 7
-
n :=숫자 크기
-
a:=새 목록
-
범위 0에서 n - 1에 있는 i에 대해 수행
-
i ~ n - 1 범위의 j에 대해 수행
-
i가 j와 같으면
-
끝에 nums[j] 삽입
-
-
그렇지 않으면
-
a
끝에 ((nums[j] + a의 마지막 요소) mod m) 삽입
-
-
-
-
목록 정렬 a
-
sm:=[인덱스 왼쪽-1에서 오른쪽으로])
의 모든 요소의 합 -
sm 모드 m을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(nums, left, right): m = 10**9 + 7 n = len(nums) a=[] for i in range(n): for j in range(i,n): if i==j: a.append(nums[j]) else: a.append((nums[j]+a[-1])%m) a.sort() sm=sum(a[left-1:right]) return sm % m nums = [1,5,2,6] left = 1 right = 5 print(solve(nums, left, right))
입력
[1,5,2,6], 1, 5
출력
20