পাইথনে প্রদত্ত অ্যারের সমস্ত উপসেট থেকে সম্ভাব্য সর্বাধিক পার্থক্যের যোগফল খুঁজুন

ধরুন আমাদের n মানের একটি অ্যারে রয়েছে (উপাদানগুলি আলাদা নাও হতে পারে)। প্রদত্ত অ্যারের সমস্ত উপসেট থেকে আমাদের সম্ভাব্য সর্বাধিক পার্থক্যের যোগফল খুঁজে বের করতে হবে। এখন বিবেচনা করুন সর্বাধিক (গুলি) যে কোনও উপসেটে সর্বাধিক মান নির্দেশ করে এবং ন্যূনতম (গুলি) সেটের সর্বনিম্ন মান নির্দেশ করে। আমাদের সমস্ত সম্ভাব্য উপসেটের জন্য সর্বোচ্চ(গুলি)-মিন(গুলি) এর যোগফল খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুটটি 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

  • যোগ_মিন :=2 * যোগ_মিন + 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