Letcode 9월 11일

문제 - 최대 곱셈이 있는 그룹 (최소한 숫자 포함) 에서 인접한 하위 그룹을 찾을 수 있는 정수 그룹nums를 지정합니다.
"""
입력: [2,3,-2,4]
산출: 6
설명:[2,3] 가장 큰 제품을 보유하고 있다.
"""
천진한 해결 방안-
가능한 모든 하위 그룹을 교체하고 최대 값을 되돌려줍니다.
암호 -

def maxProduct(self, nums: List[int]) -> int:
        ans = float('-inf')
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                ans = max(ans, reduce(lambda x,y: x*y, nums[i:j+1]))
        return ans

시간 복잡도 = O (n^2)
더 좋은 해결 방안은 두 가지 변수를 유지하고 현재 위치로 끝나는 최대 제품과 최소 제품을 저장하는 것이다.
그리고 우리는 그룹을 한 번 훑어보았고, 그룹의 모든 인덱스 i에 대해 [i]로 끝나는 최대와 최소 곱셈을 업데이트했다.색인에서 가장 큰 곱셈이 결과보다 크면 결과를 업데이트합니다.

def maxProduct(self, nums: List[int]) -> int:
        # to store the max and min ending till the previous index.
        max_ending, min_ending = 1, 1
        # to store the maximum result so far
        max_so_far = min(nums)
        for num in nums:
            temp = max_ending
            # update the max product ending at current index
            max_ending = max(num, max(num * max_ending, num* min_ending))
            # update the minimum product ending at current index
            min_ending = min(num, min(num * temp, num * min_ending))
            max_so_far = max(max_so_far, max_ending)
        return max_so_far