Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में अधिकतम सबअर्रे मिन-प्रोडक्ट खोजने का प्रोग्राम


मान लीजिए हमारे पास एक सरणी nums है, हमें nums के प्रत्येक नॉन-एम्प्टी सबअर्रे का अधिकतम मिन-प्रोडक्ट ढूंढना है। चूंकि उत्तर काफी बड़ा हो सकता है, इसे 10^9+7 के मॉड्यूलो में लौटाएं। एक सरणी का मिन-प्रोडक्ट सरणी में न्यूनतम मान को सरणी के योग से गुणा करने के बराबर होता है। उदाहरण के लिए, यदि सरणी [4,3,6] है (न्यूनतम मान 3 है) तो इसका मिन-प्रोडक्ट 3*(4+3+6) = 3*13 = 39 होगा।

उदाहरण के लिए, यदि इनपुट है nums = [2,3,4,3], तो आउटपुट 30 होगा क्योंकि हम सबअर्रे [3,4,3] लेकर परिणाम को अधिकतम कर सकते हैं, तो 3*(3+4+3) = 3*10 = 30।

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

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

  • m := 10^9+7

  • stack := एक नया स्टैक

  • rsum := 0, res := 0

  • nums के अंत में 0 डालें

  • nums में प्रत्येक इंडेक्स i और मान v के लिए

    • जब तक स्टैक खाली नहीं है और nums[स्टैक के टॉप का इंडेक्स] >= v, तब तक

      • (index, val) := स्टैक का टॉप और इसे स्टैक से पॉप करें

      • arrSum := rsum

      • यदि स्टैक खाली नहीं है, तो arrSum := rsum - स्टैक के टॉप का मान

      • res := max(res, nums[index] * arrSum)

    • rsum := rsum + v

    • स्टैक के अंत में (i, rsum) पुश करें

  • res मॉड्यूलो m लौटाएं

उदाहरण

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

def solve(nums):
    m = int(1e9+7)
    stack = []
    rsum = 0
    res = 0
    nums.append(0)
    for i, v in enumerate(nums):
        while stack and nums[stack[-1][0]] >= v:
            index, _ = stack.pop()
            arrSum = rsum
            if stack:
                arrSum = rsum - stack[-1][1]
            res = max(res, nums[index] * arrSum)
        rsum += v
        stack.append((i, rsum))
    return res % m

nums = [2,3,4,3]
print(solve(nums))

इनपुट

[2,3,4,3]

आउटपुट

30
  1. Python में इमारतों की अधिकतम ऊंचाई ज्ञात करें Python में इमारतों की अधिकतम ऊंचाई ज्ञात करें

    n इमारतें एक पंक्ति में (1 से n लेबल)। प्रतिबंध: restrictions[i] = (id, max_height)। नियम: ऊंचाई ≥ 0, पहली इमारत की ऊंचाई = 0, आसन्न इमारतों में ऊंचाई अंतर ≤ 1। अधिकतम संभव ऊंचाई खोजें। एल्गोरिदम: दो पास + शिखर गणना प्रतिबंधों को id द्वारा सॉर्ट करें फॉरवर्ड पास: बाएं से दाएं, प्रत्येक प्रतिबंध को

  1. पायथन में BST में रेंज में नोड्स की संख्या खोजने का प्रोग्राम पायथन में BST में रेंज में नोड्स की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक BST है, और हमारे पास बाएं और दाएं बाउंड l और r भी हैं, हमें रूट में उन सभी नोड्स की संख्या गिननी है जिनके मान l और r के बीच हैं (सम्मिलित)। उदाहरण के लिए, यदि इनपुट जैसा है: l = 7, r = 13, तो आउटपुट 3 होगा, क्योंकि तीन नोड्स हैं: 8, 10, 12। इसे हल करने के लिए हम निम्न चरणों

  1. - Python प्रोग्राम: तीन संख्याओं में से अधिकतम खोजें

    इस ट्यूटोरियल में, हम एक प्रोग्राम लिखेंगे जो तीन आंकड़ों में से अधिकतम राशि ढूंढता है। हमारे पास तीन संख्याएं होंगी, और हमारा लक्ष्य उन तीन संख्याओं में से अधिकतम संख्या ढूंढना है।बेहतर समझ के लिए कुछ नमूना टेस्ट केस देखें।इनपुट: a, b, c = 2, 34, 4 आउटपुट: 34इनपुट: a, b, c = 25, 3, 12 आउटपुट: 25इनप