Press "Enter" to skip to content

Posts published in “Dynamic Programming”

LeetCode 53. Maximum Subarray (javascript)

By stone on April 3, 2021

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -105 <= nums[i] <= 105

Idea:

Dynamic Programing

  • Base case: dp[0] = nums[0];
  • dp[i] = Math.max(dp[i – 1] + nums[i], nums[i]);

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // dp[i] the largest sum of subarray in nums[0...i]
    let dp = new Array(nums.length);
    // basic case:
    dp[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
    return Math.max(...dp);
};

LeetCode 5. Longest Palindromic Substring (javascript)

By stone on April 2, 2021

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters (lower-case and/or upper-case),

Idea:

Dynamic Programing

dp[i][j] = if the substring from i to j is a palindrome = true
dp[i][j] = dp[i+1][j-1] and s[i] === s[j]
base case:
dp[i][i] = true; 
dp[i][i+1] = s[i] === s[i+1];
  • Time complexity : O(n2)
  • Space complexity : O(n2)

Solution:

var longestPalindrome = function(s) {
    let len = s.length;
    if (s === null || len === 1) return s;
    let dp = Array.from(new Array(len), () => new Array(len));
    let res = "";
    let max = 0;
    
    for (let j = 0; j < len; j++) {
        // remember i <= j
        for (let i = 0; i <= j; i++) {
            let isSame = s[i] === s[j];
            
            // one and two letters palindromes only check s[i] === s[j]
            // more than 2, check subset dp[][] && s[i] === s[j]
            dp[i][j] = j - i <= 2 ? isSame : dp[i + 1][j - 1] && isSame;
            
            // any new max palindrome, update max and longest result
            if (dp[i][j] && j - i + 1 > max) {
                max = j - i + 1;
                res = s.substring(i, j + 1);
            }
        }
    }
    return res;
}