DAY9 - Dynamic Programming - Maximum Subarray Solution

maxSubarray.js

// top-down approach
function maxSubarray(arr) {
    const memo = {};
    let answer = Number.MIN_VALUE;
    
    function _maxSubarray(arr, i) {
        // base case
        if (arr.length === 0) return 0;
        if (i === 0) return arr[0];
        // induction case
        if (memo[i]) return memo[i];
        memo[i] = Math.max(_maxSubarray(arr, i - 1) + arr[i], arr[i]);
        // update answer (find max)
        if (memo[i] > answer) {
            answer = memo[i];
        }
        return memo[i];
    }
    
    _maxSubarray(arr, arr.length - 1);
    return answer;
}

// bottom-up approach
function maxSubarray(arr) {
    // base case
    if (arr.length === 0) return 0;
    const memo = {};
    memo[0] = arr[0];
    // induction case
    let answer = Number.MIN_VALUE;
    for (let i = 1; i < arr.length; ++i) {
        memo[i] = Math.max(memo[i-1] + arr[i], arr[i]);
        if (memo[i] > answer) {
            answer = memo[i];   
        }
    }
    return answer;
}