Python में सूची से प्रत्येक सबलिस्ट के न्यूनतम का योग खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। हमें nums में हर सबलिस्ट x के लिए x के न्यूनतम का योग ज्ञात करना है। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9 + 7 से मॉड करें।

इसलिए, यदि इनपुट है nums = [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 है।

हल करने का दृष्टिकोण

• ans := 0
• s := एक नई सूची
• temp_sum := 0
• nums में प्रत्येक इंडेक्स और मान के लिए, करें:
  • जब तक s और मान <= s में अंतिम सूची के इंडेक्स 1 पर तत्व, करें:
    • temp_sum := temp_sum - s में अंतिम सूची के इंडेक्स 2 पर तत्व
    • s से अंतिम तत्व हटाएं
  • यदि s खाली है, तो:
    • s में तीन तत्वों [इंडेक्स, मान, (इंडेक्स + 1)*मान] वाली सूची डालें
  • अन्यथा:
    • s में तीन तत्वों [इंडेक्स, मान, (इंडेक्स - s की अंतिम सूची का पहला तत्व)*मान] वाली सूची डालें
  • temp_sum := temp_sum + s में अंतिम सूची के इंडेक्स 2 पर तत्व
  • ans := ans + temp_sum
• ans mod (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