Leetcode’s Maximum Subarray — Solution Explained

Marika Lam

·

Follow

Jul 2, 2024

--

Share

Prompt

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
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;
};

Explanation

• This approach is called the Kadane’s Algorithm. The idea of this algorithm is to maintain a variable called maxCurrent and maxGlobal.
• maxGlobal stores the maximum sum contuous subarray ending at current index
• maxSoFar stores the maximum sum of contiguous subarray found so far.