Longest Increasing Subsequence Problem: A Deep Dive into Dynamic Programming

The Longest Increasing Subsequence (LIS) problem involves finding the length of the longest subsequence of a given sequence such that all elements of the subsequence are in increasing order.

Given an array of integers, the task is to determine the length of the LIS without actually constructing the subsequence itself. The goal is to find the maximum number of elements from the array that can be arranged in increasing order.

A dynamic programming approach is employed to solve the LIS problem efficiently. We define a 1D array, `dp`, where each element at index `i` represents the length of the longest increasing subsequence that ends with the element at index `i` in the given array.

The core idea is to iterate through the array and for each element, check all previous elements. If an element is less than the current element, it means we can extend an existing LIS by adding this element. We update the `dp[i]` value as `max(dp[i], dp[j] + 1)`, where `j` ranges from `0` to `i-1`. This step ensures that we maximize the length of the subsequence ending at each index.

Finally, the length of the LIS is found by taking the maximum value in the `dp` array.

def longest_increasing_subsequence(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

function longestIncreasingSubsequence(nums) {
    const n = nums.length;
    let dp = new Array(n).fill(1);

    for (let i = 1; i < n; 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);
}

func longestIncreasingSubsequence(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

dp := make([]int, n)
for i := range dp {
    dp[i] = 1
}

for i := 1; i < n; i++ {
    for j := 0; j < i; j++ {
        if nums[i] > nums[j] {
            dp[i] = max(dp[i], dp[j]+1)
        }
    }
}

maxLIS := dp[0]
for _, v := range dp {
    if v > maxLIS {
        maxLIS = v
    }
}
return maxLIS
}

fn longest_increasing_subsequence(nums: &mut Vec) -> i32 {
    let mut dp = vec![1; nums.len()];

    for (i, &num) in nums.iter().enumerate().skip(1) {
        for j in 0..i {
            if nums[j] < num {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }

    *dp.iter().max().unwrap()
}

The time complexity of the dynamic programming solution for the Longest Increasing Subsequence problem is O(n²). This is because we have two nested loops: one to iterate through each element in the array and another to check all previous elements. The space complexity is O(n) due to the `dp` array used to store intermediate results.

This solution is efficient for moderate-sized input arrays, but it may not scale well for very large inputs due to its quadratic time complexity.