[PS] Leet | 53. 최댓값을 가지는 하위 배열 - 덧셈

문제

Given an integer array nums, find the subarray with the largest sum, and return its sum.

예시

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

조건

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

답

첫 번째 수부터 더했을 때 가장 작은 크기의 합이 되는 부분을 찾고, 그 부분에서 부터 총합이 제일 큰 지점을 찾습니다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = nums[0];
    let sum = nums[0];

    for(let i=1; i<nums.length; i++) {
        if (0 < sum) {
            sum = sum + nums[i];
        } else {
            sum = nums[i];
        }

        if (sum > maxSum) {
            maxSum = sum;
        }
    }

    return maxSum;
};

시간복잡도 : O(n)

공간복잡도 : O(1)

 

분할 정복법으로도 구현 가능합니다.

 

이 때 subarray 별로 가장 큰 구간 구하는 법은, 중앙에서부터 좌/우로 가장 큰 합을 가지는 구간(leftMax, rightMax)을 구한 뒤, 둘을 붙여주는 것입니다.

function maxSubArray(nums) {
    function helper(left, right) {
        if (left === right) return nums[left];

        const mid = Math.floor((left + right) / 2);

        const leftSum = helper(left, mid);
        const rightSum = helper(mid + 1, right);
        const crossSum = maxCrossingSum(left, mid, right);

        return Math.max(leftSum, rightSum, crossSum);
    }

    function maxCrossingSum(left, mid, right) {
        let leftMax = -Infinity;
        let sum = 0;
        for (let i = mid; i >= left; i--) {
            sum += nums[i];
            leftMax = Math.max(leftMax, sum);
        }

        let rightMax = -Infinity;
        sum = 0;
        for (let i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightMax = Math.max(rightMax, sum);
        }

        return leftMax + rightMax;
    }

    return helper(0, nums.length - 1);
}

시간복잡도 : O(nlogn)

공간복잡도 : O(logn)