[Leet Code Top 100] #152. Maximum Product Subarray

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

첫 시도에 풀었던 방법은 단순히 이중 for loop 를 순회하면서 최대값을 찾는 방법이었습니다. O(n^2) 의 시간복잡도를 가져서 당연하게도, Time Limit Exceeded 가 발생했습니다.

그 다음 고려했던 방법은 nums[i] 요소의 제한 사항이 정수라는 것에 착안하여 0 을 제외하고는 절대값이 그 이전 값보다 같거나 클 수 밖에 없다는 점이었습니다. 답안을 보기 전에는 nums[i] 가 0 일 경우에 대해서만 고려해서 0 으로 초기화 되기 전의 값을 가져가면서 비교하는 방법이 있지 않을까 라는 생각을 했었는데 결국 구현하지는 못했습니다.

이 전에 있던 최소값이 이후에 나올 음수 값과 곱해지면서 최대값이 될 수 있도록, max 값과 min 값 두 개를 계속 가져간다는 컨셉을 생각했다면 구현할 수 있었을 것 같습니다.

 

소스 코드

// Leet Code
// #152. Maximum Product Subarray
// Success
// Runtime: 134 ms, faster than 14.16% of JavaScript online submissions for Maximum Product Subarray.
// Memory Usage: 40.1 MB, less than 80.83% of JavaScript online submissions for Maximum Product Subarray.

function main(){
    // Input
    nums = [2,3,-2,4];
    // Output
    // 6
    console.log(maxProduct(nums));
}

/**
 * @param {number[]} nums
 * @return {number}
 */
// var maxProduct = function(nums) {
//     let max = -Infinity;
    
//     for(let idx = 0; idx < nums.length; idx++){
//         let initMul = 1;
        
//         for(let jdx = idx; jdx < nums.length; jdx++){
//             initMul *= nums[jdx];
            
//             if(max < initMul){
//                 max = initMul;
//             }
//         }
//     }
    
//     return max;
// };

var maxProduct = function(nums) {
    let result = nums[0];
    let max = nums[0];
    let min = nums[0];
    
    for(let idx = 1; idx < nums.length; idx++){
        let prevMax = max;
        let prevMin = min;
        
        max = Math.max(prevMax * nums[idx], nums[idx], prevMin * nums[idx]);
        min = Math.min(prevMax * nums[idx], nums[idx], prevMin * nums[idx]);
        
        if(result < max){
            result = max;
        }
    }
    
    return result;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - Clean JavaScript solution