Pythonでの最大製品サブ配列

numsという整数配列があるとすると、最大の積を持つ配列（少なくとも1つの数値を含む）内で連続するサブ配列を見つける必要があります。したがって、配列が[2,3、-2,4]の場合、連続するサブ配列[2,3]の積が最大になるため、出力は6になります。

これを解決するには、次の手順に従います-

• max_list：=サイズ番号のリスト、0で埋める
• min_list：=サイズ番号のリスト、0で埋める
• max_list [0]：=nums[0]およびmin_list[0]：=nums [0]
• 1からnumsの長さのiの場合
  • max_list [i] =max_list [i-1] * nums [i]、min_list [i-1] *nums[i]およびnums[i]の最大値
  • min_list [i] =minof 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