पायथन में दिए गए सरणी के सभी सबसेट से संभव अधिकतम अंतर का योग ज्ञात करें

मान लीजिए कि हमारे पास n मानों की एक सरणी A है (तत्व भिन्न नहीं हो सकते हैं)। हमें दिए गए सरणी के सभी सबसेट से संभव अधिकतम अंतर का योग ज्ञात करना है। अब विचार करें कि अधिकतम (एस) किसी भी सबसेट में अधिकतम मूल्य को दर्शाता है, और न्यूनतम (एस) सेट में न्यूनतम मूल्य को दर्शाता है। हमें सभी संभावित उपसमुच्चयों के लिए अधिकतम (ओं) - मिनट (ओं) का योग ज्ञात करना होगा।

इसलिए, यदि इनपुट A =[1, 3, 4] जैसा है, तो आउटपुट 9 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=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) मॉड एन

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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