Longest Increasing Subsequence Problem: A Mathematical Dive into Dynamic Programming

The Longest Increasing Subsequence (LIS) problem is a classic algorithmic challenge that involves finding the length of the longest subsequence within an unsorted list where each element is greater than the previous one.

To solve this problem using dynamic programming, we'll use an array `dp` where `dp[i]` represents the length of the longest increasing subsequence that ends with the element at index `i`. The key idea is to build this array iteratively by comparing each element in the input array with all previous elements.

function lengthOfLIS(nums: number[]): number {
  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);
}

The time complexity of the dynamic programming solution for the Longest Increasing Subsequence problem is O(n²), where n is the length of the input array. This is because we have two nested loops, each iterating through the entire array.

The space complexity is also O(n) since we are using an additional array `dp` of size n to store the lengths of the longest increasing subsequences for each element.