หาผลรวมของความต่าง Max-Min จากทุก Subset ของอาร์เรย์ใน Python

Sum of (max - min) over all Subsets

กำหนดอาร์เรย์ A ขนาด n (อาจมีค่าซ้ำ) ต้องการหา Σ (max(S) - min(S)) สำหรับทุก Subset S ของ A

ตัวอย่าง: A = [1, 3, 4] → Subsets: {1},{3},{4},{1,3},{1,4},{3,4},{1,3,4} → ผลรวม = 9

สูตรคณิตศาสตร์ (O(N log N))

เรียงอาร์เรย์ A จากน้อยไปมาก สำหรับแต่ละ A[i]:

• เป็น max ใน 2^i subsets (เลือกจาก i ตัวแรก)
• เป็น min ใน 2^(n-1-i) subsets (เลือกจาก n-1-i ตัวหลัง)

ผลรวม = Σ A[i] * (2^i - 2^(n-1-i)) (mod 1e9+7)

โค้ดตัวอย่าง Python

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

print(get_max_min_diff([1, 3, 4]))  # 9