पायथन में एक सूची से प्रत्येक उपन्यास के न्यूनतम योग को खोजने का कार्यक्रम

मान लीजिए हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है। हमें अंकों में प्रत्येक उप-सूची 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 पर तत्व, करते हैं
    • temp_sum :=temp_sum - एस में अंतिम सूची के सूचकांक 2 पर तत्व
    • एस से अंतिम तत्व हटाएं
  • अगर s खाली है, तो
    • तीन तत्वों [सूचकांक, मान, (सूचकांक + 1)*मान] के साथ एक सूची डालें
  • अन्यथा,
    • तीन तत्वों के साथ एक सूची डालें [सूचकांक, मान, (सूचकांक - अंतिम सूची का पहला तत्व)*मान]
  • 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