Python에서 주어진 배열의 모든 하위 집합에서 가능한 최대 차이의 합 찾기

n 값의 배열 A가 있다고 가정합니다(요소는 구별되지 않을 수 있음). 주어진 배열의 모든 하위 집합에서 가능한 최대 차이의 합을 찾아야 합니다. 이제 max(s)는 하위 집합의 최대값을 나타내고 min(s)은 집합의 최소값을 나타냅니다. 가능한 모든 하위 집합에 대해 max(s)-min(s)의 합계를 찾아야 합니다.

따라서 입력이 A =[1, 3, 4]와 같으면 출력은 9가 됩니다.

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

n :=A의 크기
목록 정렬 A
sum_min :=0, sum_max :=0
0에서 n 사이의 i에 대해 수행
- sum_max :=2 * sum_max + A[n-1-i]
- sum_max :=sum_max 모드 N
- sum_min :=2 * sum_min + A[i]
- sum_min :=sum_min 모드 N
return(sum_max - sum_min + N) mod N

예시

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

N = 1000000007
def get_max_min_diff(A):
   n = len(A)
   A.sort()
   sum_min = 0
   sum_max = 0
   for i in range(0,n):
      sum_max = 2 * sum_max + A[n-1-i]
      sum_max %= N
      sum_min = 2 * sum_min + A[i]
      sum_min %= N
   return (sum_max - sum_min + N) % N
A = [1, 3, 4]
print(get_max_min_diff(A))

입력

[1, 3, 4]