5. 53. Maximum Subarray

Maximum Subarray - LeetCodeLeetCode

Time: O(n)

Space: O(1)

let currSum;
let max;
var maxSubArray = function(nums) {
    currSum = nums[0];
    max = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        max = Math.max(currSum, max);
    }

    return max;
};

Time: O() Space: O(logn)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {

    //     let maxSum = -Infinity;
    // let currSum = 0;

    // for (let i = 0; i < nums.length; i++) {
    //   const curr = nums[i];
    //   currSum = Math.max(curr, currSum + curr);
    //   maxSum = Math.max(maxSum, currSum);
    // }

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

function maxSubArraySum(arr, left, right) {
    if (left === right) return arr[left];

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

    const leftMax = maxSubArraySum(arr, left, mid);
    const rightMax = maxSubArraySum(arr, mid + 1, right);
    const crossMax = maxCrossSum(arr, mid, left, right);

    return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossSum(arr, mid, left, right) {

    // left
    let leftMaxSum = -Infinity;
    let leftSum = 0;
    for (let i = mid; i >= left; i--) {
        const curr = arr[i];
        leftSum += curr;
        leftMaxSum = Math.max(leftMaxSum, leftSum);        
    }

    // right
    let rightMaxSum = -Infinity;
    let rightSum = 0;
    for (let i = mid + 1; i <= right; i++) {
        const curr = arr[i];
        rightSum += curr;
        rightMaxSum = Math.max(rightMaxSum, rightSum);
    }

    return leftMaxSum + rightMaxSum;
}