How do i add memoization when calculating longest subsequence for an integer array?

Question

I'm doing https://leetcode.com/problems/longest-increasing-subsequence/

I know in theory that each index needs to be assigned a length but i'm having trouble coding it up using my iterative approach

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
    let maxSubsequenceLength = -Infinity;
    const stack = [[-1, 0, 0]];
    const cache = new Map();

    while (stack.length > 0) {
        const [previousIndex, currentIndex, currentLength] = stack.pop();

        if (currentIndex === nums.length) {
            maxSubsequenceLength = Math.max(maxSubsequenceLength, currentLength);
        } else {
            const previousNumber = nums[previousIndex] ?? -Infinity;
            const currentNumber = nums[currentIndex];

            if (currentNumber > previousNumber) {
                stack.push([currentIndex, currentIndex + 1, currentLength + 1]);
            }

            stack.push([previousIndex, currentIndex + 1, currentLength]);
        }
    }

    return maxSubsequenceLength;
};

Aicody · Accepted Answer · 2024-06-16 15:05:49Z

1

This is a dynamic programming problem, and you don't need an stack to solve it.
You can simply initialize an array for memoization:
The, you can create two for loops (i and j) and check every pair O(N ^ 2).
If nums[i] > nums[j]: you add one to the previously cached solution, using dp[i] = Math.max(dp[i], dp[j] + 1);

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;

  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));

To make it more efficient and optimized, you can add a binary search function:

function lengthOfLIS(nums) {
  function binarySearch(lo, hi, target) {
    while (lo <= hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (dp[mid] >= target) {
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return lo;
  }

  const dp = new Array(nums.length).fill(Infinity);
  let lis = 0;
  for (const num of nums) {
    let lo = 0,
      hi = lis;
    lo = binarySearch(lo, hi, num);
    dp[lo] = num;
    lis = Math.max(lis, lo + 1);
  }

  return lis;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));

answered Jun 16, 2024 at 15:05

Aicody

4,9063 gold badges8 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

xqcccccccccc Over a year ago

I know it's a dp problem and i was able to find many solutions on leetcode using that but i'm looking to solve it with stack + memoization, thanks for the help tho

Aicody Over a year ago

@xqcccccccccc What would you like to cache/memoize?

xqcccccccccc Over a year ago

i'm thinking to avoid repeated work, caching could be done to set max length for each index? sounds like your dp approach lol but i'm still wondering if that could be done in this dfs approach

Aicody Over a year ago

@xqcccccccccc You're already caching the max length using maxSubsequenceLength = Math.max(maxSubsequenceLength, currentLength);. You can use other methods, but there'll be a time complexity and efficiency issue that solution will fail for large test cases.

Collectives™ on Stack Overflow

How do i add memoization when calculating longest subsequence for an integer array?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related