मान लीजिए हमारे पास nums नामक एक सरणी है, हमें एक सन्निकट सबएरे के तत्वों का गुणनफल ढूंढना है जिसमें सबसे बड़ा गुणनफल हो (कम से कम एक संख्या हो)। इसलिए यदि सरणी [1,9,2,0,2,5] है, तो आउटपुट 18 होगा, क्योंकि सन्निकट सबएरे [1,9,2] का अधिकतम गुणनफल है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- max_list := nums के आकार की सूची, और 0 से भरें
- min_list := nums के आकार की सूची, और 0 से भरें
- min_list := 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([1,9,2,0,2,5]))
इनपुट
[1,9,2,0,2,5]
आउटपुट
18
