Dynamic Programming

A set of problems that can be solved using Dynamic Programming

Maximum Subarray (https://leetcode.com/problems/maximum-subarray/)

Solved using Kadanes algorithm

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) { 
    let maxSoFar = nums[0];
    let minSoFar = nums[0];
    let 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;
};

Maximum product subarray: https://leetcode.com/problems/maximum-product-subarray/

A more challenging problem can be solved using min and max variables so far and flipping them each time we will meet a minus value in the array.

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let maxProduct = nums[0];
    let maxSoFar = nums[0];
    let minSoFar = nums[0];
    
    for (let i=1; i< nums.length; i++) {
        if (nums[i] < 0) { //swap
            let temp = minSoFar;
            minSoFar = maxSoFar;
            maxSoFar = temp;
        }
        
        minSoFar = Math.min(nums[i], minSoFar * nums[i]);
        maxSoFar = Math.max(nums[i], maxSoFar * nums[i]);
        
        maxProduct = Math.max(maxSoFar, maxProduct);
        
    }
    return maxProduct;
};