Pythonで隣接するサブアレイの最大積を見つけるプログラム

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

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

• max_list：=サイズ番号のリスト、0で埋める
• min_list：=サイズ番号のリスト、0で埋める
• min_list：=サイズ番号のリスト、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([1,9,2,0,2,5]))

入力

[1,9,2,0,2,5]

出力

18