[LeetCode] 152. Maximum Product Subarray

😎풀이

처음에 해당 문제를 슬라이딩 윈도우로 풀이하려다 시간 초과로 실패했음

O(n)의 시간복잡도로 풀이하는 방식을 찾아보니 다음 풀이절차가 있음

중요 포인트는 최솟값을 갱신하는 것인데, 곱하기 연산은 음수와 음수를 곱했을 때 최댓값이 나올 수 있으므로 가장 낮은 수를 알고있어야 함

1. nums의 0번째 요소를 최댓값 및 최솟값으로 설정
2. nums를 순회하며 해당 수를 독단적으로 사용하거나, 현재 최댓값, 최솟값에 곱하며 가능한 최댓값, 최솟값을 갱신함
3. 반영된 최댓값을 반환

function maxProduct(nums: number[]): number {
    let max = nums[0]
    let curMax = nums[0]
    let curMin = nums[0]
    for(let i = 1; i < nums.length; i++) {
        const curNum = nums[i]
        const temp = curMax
        curMax = Math.max(curNum, Math.max(curNum * curMax, curNum * curMin))
        // 최대 음수는 같은 음수를 곱했을 때 최대 양수가 될 가능성이 있음
        curMin = Math.min(curNum, Math.min(curNum * temp, curNum * curMin))
        max = Math.max(max, curMax)
    }

    return max
};