Longest Increasing Subsequence
Pattern of Problems: Given an array (or list) of items and you'd have to find the largest subset of the items which maintains certain condition

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io
Problem Statement:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Solution:
Recurrence Relation:
Let arr[0..n1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.
To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
The length of the longest increasing subsequence ending at index i, will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices j such that j is before i, where arr[j] < arr[i].
Java Code:
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
int len = nums.length;
int[] dp = new int[len];
Arrays.fill(dp, 1);
int max = 1;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
Python Code:
class Solution(object):
# :type nums: List[int]
# :rtype: int
def lengthOfLIS(self, nums):
if nums == None or len(nums) == 0:
return 0
length = len(nums)
dp = [1] * length
maximum = 1
for i in range(length):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
maximum = max(maximum, dp[i])
return maximum
Track Path:
Now we will concentrate on printing the longest increasing subsequence. This is how we achieve this: for every element in the array we keep track of the element that comes immediately before it in the longest increasing subsequence. We store this data in parent[] array. Initially all the elements are the parent of its own. The code below will make this process clearer.
Java Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Use Cases:
Most problems where
you are given an array (or list) of items
and you'd have to find the largest subset of the items which maintains certain condition
could be solved using Longest Increasing Subsequence technique.
Template:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Take a look at the following problems and you would be able to have a strong grasp on how to effortlessly use the above template to solve a wide variety of problems of the pattern described in the Use Case section:
 Box Stacking
 Russian Doll Envelopes
 Largest Divisible Subset
 Longest Bitonic Subsequence
 Longest String Chain
 Best Team with No Conflict
Instructor:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn