ค้นหาผลรวมของผลต่างสูงสุดที่เป็นไปได้จากชุดย่อยทั้งหมดของอาร์เรย์ที่ระบุใน Python

สมมติว่าเรามีอาร์เรย์ A ที่มีค่า n ค่า (องค์ประกอบอาจไม่แตกต่างกัน) เราต้องหาผลรวมของผลต่างสูงสุดที่เป็นไปได้จากชุดย่อยทั้งหมดของอาร์เรย์ที่กำหนด ตอนนี้ให้พิจารณา max(s) หมายถึงค่าสูงสุดในชุดย่อยใดๆ และ min(s) หมายถึงค่าต่ำสุดในชุด เราต้องหาผลรวมของ max(s)-min(s) สำหรับ subsets ที่เป็นไปได้ทั้งหมด

ดังนั้น หากอินพุตเป็น A =[1, 3, 4] เอาต์พุตจะเป็น 9

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• เรียงลำดับรายการ A

• sum_min :=0, sum_max :=0

• สำหรับผมอยู่ในช่วง 0 ถึง 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

• ผลตอบแทน (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]

ผลลัพธ์

9