Tìm tổng hiệu lớn nhất từ tất cả các tập con của mảng trong Python

Cho mảng A gồm n giá trị (có thể trùng lặp). Ta cần tìm tổng của max(s) - min(s) cho tất cả các tập con s của mảng.

Ví dụ, với A = [1, 3, 4], kết quả là 9.

Thuật toán giải quyết

• Sắp xếp mảng A.
• Khởi tạo sum_min := 0, sum_max := 0.
• Duyệt i từ 0 đến n-1:
  • sum_max = 2 * sum_max + A[n-1-i] (mod N).
  • sum_min = 2 * sum_min + A[i] (mod N).
• Trả về (sum_max - sum_min + N) % N với N = 1_000_000_007.

Ví dụ minh họa

N = 1000000007

def get_max_min_diff(A):
    n = len(A)
    A.sort()
    sum_min = 0
    sum_max = 0
    for i in range(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))  # 9

Đầu vào

[1, 3, 4]

Đầu ra

9