Maximum sum subarray

contiguous-sum.js

function findMaxSum(arr) {
    let highestSum = 0
    let nextSum = 0

    for (let i = 0; i < arr.length; i++) {
        nextSum = 0
        for (let j = i; j < arr.length; j++) {
            nextSum += arr[j]
            if (nextSum > highestSum) {
                highestSum = nextSum
            }
        }
    }
    return highestSum
}

/**
 *  This algorithm uses Kadane's algorithm to find 
 * maximum sum subarray in an array
 */
function findMaxSumKadane(arr) {
    // return null when the arr is empty or null, as empty array is not valid input
    if (!arr || arr.length == 0) return null

    // set currentMaxSum to first element of the array
    let currentMaxSum = arr[0]

    // set globalMaxSum to first element of the array
    let globalMaxSum = arr[0]

    for (let i = 1; i < arr.length; i++) {
        /**
         *  Compare the previous max sum + current element of the subarray with 
         *  the value of new element and update the current max sum
         */
        currentMaxSum = Math.max(arr[i], currentMaxSum + arr[i])
        
        /**
         * If currentMaxSum is greater than the global, then 
         * update the globalMaxSum too
         */
        if (currentMaxSum > globalMaxSum) {
            globalMaxSum = currentMaxSum
        }
    }

    // Return the globalMaxSum as its the actual answer
    return globalMaxSum
}

// Input array
const inputArr = [-5, 6, 7, 1, 4, -8, 16]

// Test with brute force algorithm
console.log(findMaxSum(inputArr))

// Test with Kadane's algorithm
console.log(findMaxSumKadane(inputArr))