Python의 최대 곱 하위 배열

<시간/>

num이라는 정수 배열이 있다고 가정하고 가장 큰 곱을 갖는 배열(최소한 하나의 숫자를 포함) 내에서 연속적인 하위 배열을 찾아야 합니다. 따라서 배열이 [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]