[LeetCode] 152. Maximum Product Subarray (JS)

https://leetcode.com/problems/maximum-product-subarray/

Maximum Product Subarray - LeetCode

핵심 아이디어

• (n-1)번째 local max 와 연산해서 n번째 local max를 구할 수 있으므로 DP. 그러나 (n-1)번째 지역해만을 사용하기 때문에 배열은 만들지 않고 localMin, localMax 변수 2개로 지역해를 트래킹했다
  
  • 정수를 곱하면 절댓값이 커지는 곱하기 연산의 특징 때문에 DP를 연상할 수 있다
• 음수를 곱하면 절댓값은 커지지만 전체 결과가 음수가 되면 작아지므로, localMin은 계속 트래킹해야 한다

 

복잡도

• 시간 복잡도: O(n)
  
  • 배열 1회 순회하면서 localMax, localMin, result 비교 연산
• 공간 복잡도: O(1)
  
  • n-1번째 결과만 사용하므로 배열 대신 localMax, localMin 두 개의 값으로 지역해 트래킹

 

설명

배열에서 연속된 부분 배열의 최대 곱을 찾는 문제이다. 음수가 포함되는데, 음수가 짝수 번 곱해져서 양수가 되면 그게 답이 될 수 있다는 점 때문에 까다롭다.

연속된 배열의 곱을 구하는 것이기 때문에 localMax(n) = Max( localMax(n-1) * n, localMin(n-1) * n, n)  과 같은 점화식을 세울 수 있다. 즉, 1) 이전 최대 연속곱에 추가로 n을 곱하거나 2) 이전 최소 연속곱에 n을 곱하거나, 3) 아니면 그냥 n으로 새로 시작하는 선택 중에서 가장 큰 값으로 지역해를 구할 수 있는 것이다. 2)번이 비교 조건에 들어간 것은, 음수 * 음수 = 양수 case가 있을 수 있기 때문이다. 그래서 절댓값이 가장 클 수도 있는 localMin을 트래킹한다. 3)이 선택되는 경우는 n부터 부분 배열을 새로 시작하는 case이다.

이렇게 구한 localMax들 사이에서 가장 큰 값이 이 문제의 해답인 result가 된다. 그러나 max 연산은 하나씩 비교해도 무방하므로 for문 안에 넣어서 하나씩 비교했다.

주의해야 할 점은 localMin = Math.min(localMaxTemp * num, localMin * num, num); 에서 localMax 대신에 localMaxTemp를 썼다는 점이다. 이는 localMax가 앞줄에서 변경되었기 때문에, localMax(n-1) 을 사용하기 위해서 값을 미리 localMaxTemp에 저장해 놓은 것이다.

또, edge 케이스로는 num === 0 인 경우가 있는데, 0은 곱을 0으로 만들어 버린다. 그러나 이 경우에는 다음 번째에서 localMax 또는 localMin으로 num (0 다음 값) 이 선택될 것이므로 주어진 식으로 커버할 수 있다.

 

코드 (Javascript)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let result = nums[0];
    let localMax = 1;
    let localMin = 1;
    let localMaxTemp = localMax;
    
    for (num of nums) {      
        localMaxTemp = localMax;
        localMax = Math.max(localMax * num, localMin * num, num);
        localMin = Math.min(localMaxTemp * num, localMin * num, num);
        result = Math.max(localMax, result);
    }
    
    return result;
};

 

유튜브 NeetCode 해설 영상