পাইথনের একটি তালিকা থেকে প্রতিটি সাবলিস্টের ন্যূনতম যোগফল খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে বলা হয় সংখ্যা। আমাদের প্রতিটি সাবলিস্ট x-এর জন্য ন্যূনতম x-এর যোগফল বের করতে হবে। যদি উত্তরটি খুব বড় হয়, তাহলে ফলাফলটি 10^9 + 7 দ্বারা পরিবর্তন করুন।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[5, 10, 20, 10, 0], তাহলে আউটপুট 90 হবে কারণ, সাবলিস্টগুলি হল [[5], [10], [20], [10], [ 0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0] , [5,10,20,10], [10,20,10,0], [5,10,20,10,0]], এবং তাদের সর্বনিম্ন মান হল [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0], তাই যোগফল 90।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=0
• s :=একটি নতুন তালিকা
• temp_sum :=0
• প্রতিটি সূচক এবং মানের জন্য, করুন
  • যখন s এবং মান <=s এ শেষ তালিকার সূচী 1-এ উপাদান, do
    • temp_sum :=temp_sum - s এ শেষ তালিকার সূচী 2 এ উপাদান
    • s থেকে শেষ উপাদান মুছুন
  • যদি s খালি হয়, তাহলে
    • s-এ তিনটি উপাদান [index, value, (index + 1)*value] সহ একটি তালিকা সন্নিবেশ করান
  • অন্যথায়,
    • তিনটি উপাদান সহ একটি তালিকা সন্নিবেশ করান [সূচী, মান, (সূচী - গুলির শেষ তালিকার প্রথম উপাদান)* মান]
  • temp_sum :=temp_sum + s এ শেষ তালিকার সূচী 2 এ উপাদান
  • উত্তর :=উত্তর + temp_sum
• উত্তর মোড (10^9 + 7)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(nums):
   ans = 0
   s = []
   temp_sum = 0
   for index, value in enumerate(nums):
      while s and value <= s[-1][1]:
         temp_sum -= s[-1][2]
         s.pop()
      if not s:
         s.append([index, value, (index + 1) * value])
      else:
         s.append([index, value, (index - s[-1][0]) * value])
      temp_sum += s[-1][2]
      ans += temp_sum
   return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

ইনপুট

[5, 10, 20, 10, 0]

আউটপুট

90