Learning Journal

2/29/2024

Maximum Subarray - Kadane's algorithm

Tags: algorithms leetcode dynamic_programming

function maxSubArray(nums: number[]): number {
    let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0
    for (let i = 0; i < nums.length; i++) {
        maxEndingHere = maxEndingHere + nums[i]
        if (maxSoFar < maxEndingHere) {
            maxSoFar = maxEndingHere
        }
        if (maxEndingHere < 0)
            maxEndingHere = 0
    }
    return maxSoFar
};function maxSubArray(nums: number[]): number {
    let maxSoFar = Number.MIN_SAFE_INTEGER, maxEndingHere = 0
    for (let i = 0; i < nums.length; i++) {
        maxEndingHere = maxEndingHere + nums[i]
        if (maxSoFar < maxEndingHere) {
            maxSoFar = maxEndingHere
        }
        if (maxEndingHere < 0)
            maxEndingHere = 0
    }
    return maxSoFar
};

THE PROBLEM

This is the approach using Kadane's algorithm, in which we keep the running sum (maxEndingHere), this variable will be the max sum of all subarray that ends at i. If that sum is negative, the subarray has no use for all array suffix it, so we reset maxEndingHer to 0.