문제

53. Maximum Subarray
    Solved
    Medium
    Topics
    Companies
    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.
 

Constraints:
  1 <= nums.length <= 10^5
  -10^4 <= nums[i] <= 10^4
 

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

해답

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
   return dividedAndConquer(nums, 0, nums.length - 1);
};

function dividedAndConquer(nums, left, right) {
    if (left === right) {
        return nums[left];
    }

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

    const leftMax = dividedAndConquer(nums, left, mid);
    const rightMax = dividedAndConquer(nums, mid + 1, right);

    let leftSum = Number.MIN_SAFE_INTEGER;
    let rightSum = Number.MIN_SAFE_INTEGER;
    let sum = 0;

    for (let i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    sum = 0;

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

    return Math.max(leftMax, rightMax, leftSum + rightSum);
}