Knowledge Base | Daily Notes

Longest Increasing Subsequence

Aug 30, 20244 min read

Approach

  • tails array always has to be sorted
def lengthOfLIS(arr):
    if not arr:
        return 0
 
    n = len(arr)
    tails = [0] * n
    length = 1  # Length of LIS initialized to 1 since the first element itself is a valid LIS.
 
    tails[0] = arr[0]
 
    for i in range(1, n):
        print(tails)
        if arr[i] > tails[length - 1]:
            tails[length] = arr[i]
            length += 1
        else:
            # Find the index using binary search to update tails
            left, right = 0, length - 1
            while left < right:
                mid = (left + right) // 2
                print("mid "+ str(mid), "val "+ str(arr[i]))
                if tails[mid] < arr[i]:
                    left = mid + 1
                else:
                    right = mid
            tails[left] = arr[i]
 
    return length
 
# Example usage:
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80, 1, 2, 3, 4, 5, 6, 7]
print(lengthOfLIS(arr))  # Output: 6 (Longest Increasing Subsequence: [10, 22, 33, 50, 60, 80])

Code using Dynamic programming

# Dynamic programming Python implementation
# of LIS problem
 
 
# lis returns length of the longest
# increasing subsequence in arr of size n
def lis(arr):
	n = len(arr)
 
	# Declare the list (array) for LIS and
	# initialize LIS values for all indexes
	lis = [1]*n
 
	# Compute optimized LIS values in bottom up manner
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j]+1
 
	# Initialize maximum to 0 to get
	# the maximum of all LIS
	maximum = 0
 
	# Pick maximum of all LIS values
	for i in range(n):
		maximum = max(maximum, lis[i])
 
	return maximum
 
 
# Driver program to test above function
if __name__ == '__main__':
	arr = [10, 22, 9, 33, 21, 50, 41, 60]
	print("Length of lis is", lis(arr))
  • What is the internal if condition doing?
  • Ans. Here’s an explanation of what this code does:

    • arr[i] > arr[j] checks if the element at index i in arr is greater than the element at index j. This condition ensures that we are considering only increasing subsequences.

    • lis[i] < lis[j] + 1 checks if the length of the LIS ending at index i is less than the length of the LIS ending at index j incremented by 1. If this condition is true, it means that we have found a longer LIS ending at index i, so we update lis[i] accordingly.

    • If both conditions are met, lis[i] is updated to lis[j] + 1. This means that we have found a longer LIS ending at index i than what we previously knew

Javascript

function lengthOfLISMemo(nums) {
    const memo = new Map();
 
    function helper(prevIndex, currentIndex) {
        if (currentIndex === nums.length) {
            return 0;
        }
 
        const key = prevIndex + "," + currentIndex;
        if (memo.has(key)) {
            return memo.get(key);
        }
 
        let include = 0;
        if (prevIndex === -1 || nums[currentIndex] > nums[prevIndex]) {
            include = 1 + helper(currentIndex, currentIndex + 1);
        }
 
        const exclude = helper(prevIndex, currentIndex + 1);
        const maxLength = Math.max(include, exclude);
        memo.set(key, maxLength);
 
        return maxLength;
    }
 
    return helper(-1, 0);
}
 
// Example usage:
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLISMemo(nums)); // Output: 4
 
function lengthOfLISTab(nums) {
    const n = nums.length;
    const 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);
}
 
// Example usage:
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lengthOfLISTab(nums)); // Output: 4

Applications

  1. Stock Prices:

    • Consider a scenario where you have the daily closing prices of a stock. The Longest Increasing Subsequence would represent the longest period where the stock consistently increased in value. This example is relatable and ties in with financial data analysis.

  2. Course Scheduling:

    • Imagine you are a student planning your course schedule. Each course has a specific difficulty level, and you want to find the longest sequence of courses that gradually increase in complexity. This mirrors the Longest Increasing Subsequence problem.

  3. Path Planning in Robotics:

    • Apply the concept to a robot navigating through a grid. The robot’s path would be the sequence, and you want to find the longest increasing subsequence to optimize its route, perhaps based on energy consumption or time.

  4. DNA Sequencing:

    • Consider a DNA sequence where each nucleotide represents a different element. The Longest Increasing Subsequence could represent the longest sequence of compatible nucleotides, which is crucial in bioinformatics.

  5. Social Media Engagement:

    • Think of a scenario where a social media user is posting content over time. The likes or engagement on each post can be seen as a sequence, and finding the Longest Increasing Subsequence could highlight the user’s most successful content streak.

Graph View

Backlinks