AlgoDaily - Longest Increasing Subsequence

Mark As Completed Discussion

Code for LIS using Dynamic Programming

Finally, here's the code for implementing LIS using dynamic programming in a few different languages. As always, we advise you to work everything out on a piece of paper before implementing anything.

xxxxxxxxxx
 
// Dynamic programming solution
const longestIncreasingSubsequence = function (nums) {
  // Create an array to memoize
  const dpMemo = Array.from(nums, () => 1);
  // Initialize subsequence length
  let max = 1;
  // Check all increasing subsequences up to the current ith number in nums
  for (let i = 1; i < nums.length; i++) {
    // Keep track of subsequence length in the dpMemo array
    for (let j = 0; j < i; j++) {
      // Only change dpMemo value if the numbers are increasing
      if (nums[i] > nums[j]) {
        // Set the value to be the larget subsequence length
        dpMemo[i] = Math.max(dpMemo[i], dpMemo[j] + 1);
        // Check if this subsequence is the largest
        max = Math.max(dpMemo[i], max);
      }
    }
  }
  return max;
};
​
const result = longestIncreasingSubsequence([
  5, 15, 8, 7, 4, 10, 20, 19, 7, 25, 29, 11,
]);
console.log(result);