Longest Increasing Subsequence
A dynamic programming problem to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
Visualization
Details
Analogy
Imagine a line of people of different heights. You want to pick a smaller group of people from this line, keeping them in their original order, such that they are arranged from shortest to tallest. The goal is to find the largest possible group you can form this way.
Purpose
To find the longest subsequence where elements are in strictly increasing order. The elements do not have to be contiguous.
Use Cases
Used in data analysis, bioinformatics (analyzing gene sequences), and string matching algorithms.
Algorithm Steps
create dp array of size n, fill with 1
for i = 1 to n-1:
for j = 0 to i-1:
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Explanation
What's Happening?
Initial array. We will build a DP array representing the length of the LIS ending at each index.
Code Implementation
def length_of_lis(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)