Python中乘積最大的子陣列

假設我們有一個名為 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

Arnab Chakraborty

更新於: 2020 年 5 月 4 日

1K+ 瀏覽量

Kickstart 你的 職業生涯

完成課程獲得認證

立即開始