Python에서 숫자 목록의 모든 하위 시퀀스 너비의 합을 찾는 프로그램

<시간/>

nums라고 하는 숫자 목록이 있다고 가정합니다. 숫자 시퀀스의 너비는 시퀀스의 최대 수와 최소 수의 차이입니다. num의 모든 부분열의 너비의 합을 찾아야 합니다. 답이 매우 크면 결과를 10^9+7로 수정합니다.

따라서 입력이 nums =[7, 4, 9]와 같으면 출력은 [7], [4], [9], [7, 4], [ 7, 9], [4, 9], [7, 4, 9] 따라서 너비는 0, 0, 0, 3, 2, 5, 5이므로 15를 얻습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

m :=10^9 + 7
목록 번호 정렬
답변 :=0
power :=(nums + 1)과 크기가 같고 1로 채워진 목록
범위 1에서 숫자 + 1의 크기까지 i에 대해 수행
- power[i] :=power[i - 1] * 2 mod m
- 범위 0에서 숫자 크기까지의 i에 대해
  - 양수 :=(power[i] - 1) * nums[i]
  - 음수 :=(power[숫자의 크기 - i - 1] - 1) * nums[i]
  - ans :=(ans + 양수 - 음수) mod m
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, nums):
      m = 10**9 + 7
      nums.sort()
      ans = 0
      power = [1] * (len(nums) + 1)
      for i in range(1, len(nums) + 1):
         power[i] = power[i - 1] * 2 % m
      for i in range(0, len(nums)):
         positive = (power[i] - 1) * nums[i]
         negative = (power[len(nums) - i - 1] - 1) * nums[i]
         ans = (ans + positive - negative) % m
      return ans
ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))

입력

[7, 4, 9]