पायथन में दिए गए ऐरे के सभी उपसमुच्चयों से अधिकतम अंतर का योग खोजें

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

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

समाधान दृष्टिकोण

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

• n := len(A)
• सूची A को सॉर्ट करें।
• sum_min := 0, sum_max := 0
• i को 0 से n-1 तक के लिए:
  • sum_max := 2 * sum_max + A[n-1-i]
  • sum_max := sum_max % MOD
  • sum_min := 2 * sum_min + A[i]
  • sum_min := sum_min % MOD
• (sum_max - sum_min + MOD) % MOD लौटाएं।

उदाहरण

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

MOD = 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 %= MOD
        sum_min = 2 * sum_min + A[i]
        sum_min %= MOD
    return (sum_max - sum_min + MOD) % MOD

A = [1, 3, 4]
print(get_max_min_diff(A))

इनपुट

[1, 3, 4]

आउटपुट

9