Tìm tổng của sự khác biệt lớn nhất có thể có từ tất cả các tập con của một mảng đã cho bằng Python

Giả sử chúng ta có một mảng A gồm n giá trị (các phần tử có thể không phân biệt). Chúng ta phải tìm tổng của hiệu số lớn nhất có thể từ tất cả các tập con của mảng đã cho. Bây giờ hãy xem xét max (các) biểu thị giá trị lớn nhất trong bất kỳ tập hợp con nào và (các) min biểu thị giá trị nhỏ nhất trong tập hợp. Chúng ta phải tìm tổng (các) -min (s) tối đa cho tất cả các tập con có thể có.

Vì vậy, nếu đầu vào là A =[1, 3, 4], thì đầu ra sẽ là 9.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• sắp xếp danh sách A

• sum_min:=0, sum_max:=0

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • sum_max:=2 * sum_max + A [n-1-i]

  • sum_max:=sum_max mod N

  • sum_min:=2 * sum_min + A [i]

  • sum_min:=sum_min mod N

• return (sum_max - sum_min + N) mod N

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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))

Đầu vào

[1, 3, 4]

Đầu ra

9