मान लीजिए हमारे पास एक सरणी 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