[Leet Code Top 100] #53. Maximum Subarray

문제 정보

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

 

해결 방법

이전에 풀었던 문제 중 #121. Best Time to Buy and Sell Stock 을 카데인 알고리즘 (Dynamic Programming) 으로 풀었을 때와 동일한 문제였습니다. dp[i] 를 i 번째 인덱스를 가장 오른쪽 끝으로 하는 subArray 의 최대값으로 정의 후 구현하면 기존 dp[i - 1] 에 현재 값인 nums[i] 를 더하거나 혹은 nums[i] 로 subArray 를 시작하는 경우로 나눌 수 있습니다. 이렇게 풀이할 경우 nums 의 길이만큼 for loop 를 1회 수행하므로 시간복잡도는 O(n) 이 됩니다.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

위와 같은 추가 요건이 있었는데 최대 연속 부분수열합을 구하는 방법 중 1가지인 divide and conquer 알고리즘을 사용하는 것이었습니다. 카데인 알고리즘에 비해서 시간이 오래걸리긴 하지만 절반씩 나누어 찾아들어가는 시간이 O(log n) 이므로 middle 을 구할 때 O(n) 까지 계산하면 총 시간복잡도는 O(nlog n) 입니다.

 

소스 코드

// Leet Code
// #53. Maximum Subarray
// Success
// Runtime: 201 ms, faster than 5.02% of JavaScript online submissions for Maximum Subarray.
// Memory Usage: 49.3 MB, less than 13.93% of JavaScript online submissions for Maximum Subarray.

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

/**
 * @param {number[]} nums
 * @return {number}
 */
// var maxSubArray = function(nums) {
//     const dp = []; // dp[i] : maximum subarray value which right point is i
    
//     let max = 0;
//     for(let idx = 0; idx < nums.length; idx++){
//         if(idx === 0){
//             dp[idx] = nums[idx];
//             max = dp[idx];
//             continue;
//         }
        
//         dp[idx] = dp[idx - 1] + nums[idx] > nums[idx] ? dp[idx - 1] + nums[idx] : nums[idx];
//         if(max < dp[idx]){
//             max = dp[idx];
//         }
//     }
    
//     return max;
// };

var maxSubArray = function(nums) {
    const dp = []; // dp[i] : maximum subarray value which right point is i
    
    let max = 0;

    // case 1. low                mid             high
    //          |---=== sol ===---|-----------------|

    // case 2. low                mid             high
    //          |-----------------|---=== sol ===---|

    // case 3. low               mid              high
    //          |-----------=== sol ===-------------|

    const divideNconquer = function(low, high){
        if(low === high){
            return nums[low];
        }

        const mid = Math.floor((low + high) / 2);
        
        let leftPart = 0;
        let leftMax = -Infinity
        for(let idx = mid; low <= idx; idx--){
            leftPart += nums[idx];

            if(leftMax < leftPart){
                leftMax = leftPart;
            }
        }

        let rightPart = 0;
        let rightMax = -Infinity
        for(let jdx = mid + 1; jdx <= high; jdx++){
            rightPart += nums[jdx];

            if(rightMax < rightPart){
                rightMax = rightPart;
            }
        }

        const middle = leftMax + rightMax;
        const left = divideNconquer(low, mid);
        const right = divideNconquer(mid + 1, high);
        
        return Math.max(left, right, middle);
    }

    max = divideNconquer(0, nums.length - 1);
    
    return max;
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• Javascript Divide and Conquer (with BONUS pictures!)
• Javascript // very clear and short DP solution
• 최대 연속 부분수열 합을 구하는 4가지 알고리즘