152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

My Answer 1: Time Limit Exceeded (186 / 187 test cases passed.)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        maximum = max(nums)
        
        for i in range(len(nums)):
            product = nums[i]
            for j in range(i+1, len(nums)):
                product *= nums[j]
                maximum = max(maximum, product)
        
        return maximum

어김없이 이중 for 문 썼구요.. 약속이라도 한 듯 타임리밋 만났읍니다.

maximum 을 nums 중 max 값으로 잡고 반복문 돌리면서 product 값의 최댓값 찾기

항상 마지막 테스트 케이스는 미친 길이의 input 이군요..^^

KADANES ALGORITHM

Solution 1: Runtime: 64 ms - 21.23% / Memory Usage: 14.3 MB - 86.52%

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ## RC ##
        ## APPROACH : KADANES ALGORITHM ##
        
		## TIME COMPLEXITY : O(N) ##
		## SPACE COMPLEXITY : O(1) ##
        
        # 1. Edge Case : Negative * Negative = Positive
        # 2. So we need to keep track of minimum values also, as they can yield maximum values.
        
        global_max = prev_max = prev_min = nums[0]
        for num in nums[1:]:
            curr_min = min(prev_max*num, prev_min*num, num)
            curr_max = max(prev_max*num, prev_min*num, num)
            global_max= max(global_max, curr_max)
            prev_max = curr_max
            prev_min = curr_min
        return global_max

왜 curr_min, max 와 prev_min, max 를 쓰는지 잘 모르겠어요...

KADANES ALGORITHM 참고: https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29