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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

मी :=10^9+7
स्टैक :=एक नया स्टैक
rsum :=0, Res :=0
अंकों के अंत में 0 डालें
प्रत्येक अनुक्रमणिका के लिए i और मान v अंकों में, करें
- जबकि स्टैक खाली नहीं है और अंक [स्टैक के शीर्ष का सूचकांक]>=v, करते हैं
  - index, val) :=स्टैक के ऊपर और इसे स्टैक से पॉप करें
  - arrSum:=rsum
  - यदि स्टैक खाली नहीं है, तो
    - arrSum:=rsum - स्टैक के शीर्ष का मान
  - res:=अधिकतम रेस और (nums[index]*arrSum)
- rsum :=rsum + v
- स्टैक के अंत में पुश (i, rsum) करें
रिटर्न रेस मॉड एम

उदाहरण

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

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]