मान लीजिए हमारे पास nums नामक एक पूर्णांक ऐरे है, हमें एक ऐरे के भीतर सन्निकट सबएरे (कम से कम एक संख्या युक्त) ढूंढना है जिसका सबसे बड़ा उत्पाद हो। इसलिए यदि ऐरे [2,3,-2,4] है, तो आउटपुट 6 होगा, क्योंकि सन्निकट सबएरे [2,3] का अधिकतम उत्पाद है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- max_list := nums के आकार की लिस्ट, और 0 से भरें
- min_list := nums के आकार की लिस्ट, और 0 से भरें
- max_list[0] := nums[0] और min_list[0] := nums[0]
- i को 1 से nums की लंबाई तक की रेंज में
- max_list[i] = max_list[i - 1]*nums[i], min_list[i - 1]*nums[i] और nums[i] का अधिकतम
- min_list[i] = min_list[i - 1]*nums[i], nums[i], max_list[i - 1]*nums[i] का न्यूनतम
- max_list का अधिकतम लौटाएं
यह डायनामिक प्रोग्रामिंग दृष्टिकोण नकारात्मक संख्याओं को संभालने के लिए प्रत्येक इंडेक्स पर अधिकतम और न्यूनतम उत्पाद दोनों को ट्रैक करता है।
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
class Solution(object):
def maxProduct(self, nums):
max_list = [0] * len(nums)
min_list = [0] * len(nums)
max_list[0] = nums[0]
min_list[0] = nums[0]
for i in range(1, len(nums)):
max_list[i] = max(max(max_list[i-1]*nums[i], min_list[i-1]*nums[i]), nums[i])
min_list[i] = min(min(min_list[i-1]*nums[i], nums[i]), max_list[i-1]*nums[i])
return max(max_list)
ob1 = Solution()
print(ob1.maxProduct([2, 3, -2, 4, -5, -6, 2]))
इनपुट
[2,3,-2,4,-5,-6,2]
आउटपुट
240