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

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
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].
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;
}
}
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.
class Solution {
// Track Path
public int lengthOfLIS(int[] nums) {
if (nums == null  nums.length == 0) {
return 0;
}
int len = nums.length;
int[] dp = new int[len];
int[] parent = new int[len]; // to track path
// initialize
Arrays.fill(dp, 1);
for (int i = 0; i < len; i++) {
parent[i] = i;
}
int max = 1;
int end = 0; // end index of the longest increasing subsequence
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
if (max < dp[i]) {
max = dp[i];
end = i;
}
}
// print path
Deque<Integer> stack = new ArrayDeque();
while (parent[end] != end) {
stack.push(nums[end]);
end = parent[end];
}
stack.push(nums[end]);
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
return max;
}
}
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:
public int solve(int[] nums) {
int len = nums.length;
int[] lis = new int[len];
Arrays.fill(lis, APPROPRIATE_VALUE); // APPROPRIATE_VALUE will vary from problem to problem depending on the problem statement
int max = 1;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (condition(nums[i], nums[j])) { // implementation of condition() method will vary according to the given problem statement
dplisi] = Math.max(lis[i], lis[j] + value_for_nums_i)); // value_for_nums_i will be determined according to the problem statement
}
}
max = Math.max(max, lis[i]);
}
return max;
}
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
The above content is written by:
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