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: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.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:
Login to Access Content
Python Code:
Login to Access Content
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:
Login to Access Content
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