Coding Interview Prep: Maximum Subarray with Explained Solution in JavaScript

Solution

/*
Time Complexity: O(n)
Space Complexity: O(1)
Runtime: 48 ms
 */
var maxSubArray = function(nums) {
    let maxCurrent = nums[0];
    let maxGlobal = nums[0];
    for (let i=1; i<nums.length; i++){
        maxCurrent = Math.max(nums[i], maxCurrent+nums[i]);
        if (maxCurrent > maxGlobal){
            maxGlobal = maxCurrent;
        }
    }
    return maxGlobal;
};

Kadane’s Algorithm is used here. The idea of this algorithm is to maintain a variable maxCurrent and maxGlobal. maxCurrent stores the maximum sum contiguous subarray ending at current index and maxGlobal stores the maximum sum of contiguous subarray found so far.

The time complexity is O(n) because we loop through the elements of the array only once. The space complexity is O(1) because only constant extra space is being used.