In this article we'll see how to write a Java program to find the length of the longest increasing subsequence in the given array.
For 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.
2. Input: nums = [2, 0, 1, 7, 5, 9]
Output: 4
Explanation: The longest increasing subsequence is [0, 1, 7, 9] therefore the length is 4.
3. Input: nums = [4, 4, 4, 4, 4]
Output: 1
The "Longest Increasing Subsequence" problem is a good example of dynamic programming as you can break this problem into smaller overlapping sub-problems and you can also store the result of those subproblems (memoization) to avoid redundant calculations.
Longest Increasing Subsequence Java Program
The program for finding the length of longest increasing subsequence can be written using
- Recursion,
- You can add memoization with recursion to make it faster this is also called top-down approach in dynamic programming.
- You can also use bottom-up approach also known as tabular form. In bottom-up approach you try to solve the sub-problems first and use their solutions to arrive at solutions to bigger sub-problems.
We'll write java programs for all these three approaches here.
1. Using recursion
Let's try to understand what we need to do with an example. Suppose our elements are {9, 10, 11, 12} and i represents current element index and p represents previous element index. If i is pointing at 10 and p at 9 then we'll have to check if(arr[i] > arr[p]) for subsequence.
If condition evaluates to true then we have to do the same comparison for 10 and 11 which means incrementing i by 1 i.e. i=i+1 and assigning previous value of i to p. This is the include scenario and the length of the subsequence increases by one.
Now suppose our elements are {9, 8, 10, 11}. Again, if we check if(arr[i] > arr[p]) for subsequence it evaluates to false for arr[i] = 8 and arr[p] = 9. In this case, you won't change value of p only increment i by 1. That means arr[i]=10 and arr[p]=9. This is excluding scenario where length of the subsequence doesn't increase.
Here is the complete Java program with this approach.
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
int[] arr = {10, 9, 2, 5, 3, 7, 1, 8};
System.out.println(Arrays.toString(arr));
System.out.println(longestSubsequence(arr, 0, -1));
}
// Using dynamic programming - recursion
private static int longestSubsequence(int[] arr, int i, int p) {
// exit condition
if(i == arr.length) {
return 0;
}
int max = 0;
int include = 0;
// don't take scenario- where you just increase the index
int res = longestSubsequence(arr, i+1, p);
if(p == -1 || arr[i] > arr[p]) {
// take scenario- where you increase index and previous index
include = longestSubsequence(arr, i+1, i)+1;
}
max = Math.max(res, include);
return max;
}
}
Output
[10, 9, 2, 5, 3, 7, 1, 8] 4
You call the method with i = 0 and p = -1. Then you have exclude scenario where index of the current element is incremented. Length is not increased as the element is not included in the subsequence.
In the include scenario (arr[i] > arr[p]), both p and i are changed. Length is also increased by 1 (longestSubsequence(arr, i+1, i) + 1) as element is included in the subsequence.
The variable res stores the length of LIS based on p (arr[i] is skipped) whereas variable include stores the length of LIS based on i (arr[i] is included). Since you need the maximum LIS length so you take the max of these two scenarios.
Time and space complexity with this approach
With this approach recursive method explores all subsequences of the array and the number of subsequences of an array of length n is 2n. Therefore the time complexity is O(2n).
Recursion stack depth will be n as we move forward by one index with each method call. So, the space complexity is O(n).
2. Using memoization with recursion.
With the above recursive method there are many repetitive calls with each recursive method for the same i and p value.
What if we use an array to store previous computation values and with each computation we first make a check in the array to see if that computation is already done. That's what we do with memoization approach.
Our method has two parameters i and p so we need a 2D array having row and column length same as the length of input array. This 2D array is initialized with -1 as initial value to indicate no value is stored yet.
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
int[] arr = {10, 9, 2, 5, 3, 7, 1, 8};
// for memoization
int[][]dp= new int[arr.length][arr.length];
for(int[] a:dp) {
Arrays.fill(a, -1);
}
System.out.println(Arrays.toString(arr));
System.out.println(longestSubsequenceWithM(arr, 0, -1,dp));
}
// Using dynamic programming - recursion with Memoization
private static int longestSubsequenceWithM(int[] arr, int i, int p, int[][] dp) {
if(i == arr.length) {
return 0;
}
int max = 0;
int include = 0;
// [p+1] because p can be -1
// Check if value is already calculated for the passed i and p,
// if yes then return the same value
if(dp[i][p+1] != -1) {
return dp[i][p+1];
}
// don't take scenario where you just increase the index
int res = longestSubsequenceWithM(arr, i+1, p, dp);
if(p == -1 || arr[i] > arr[p]) {
// take scenario where you increase index and previous index
include = longestSubsequenceWithM(arr, i+1, i, dp)+1;
}
max = Math.max(res, include);
dp[i][p+1] = max;
return max;
}
}
Output
[10, 9, 2, 5, 3, 7, 1, 8] 4
Time and space complexity with this approach
With memoization, the time complexity becomes O(n2) as each state (i and p) is computed once, rest of the times it is extracted from the dp array.
Space needed is O(n2) for the dp array and O(n) for recursion stack. So the space complexity can be considered as O(n2).
3. With tabulation (Bottom-up) approach.
With this approach for finding the length of the longest increasing subsequence, iterative logic is used. A 1D array of size n is used to store the values where dp[i] stores the length of the longest increasing subsequence ending at index i. Initially, every dp[i] = 1 because each element is a subsequence of length 1 by itself.
There are two loops in the logic, in each iteration of the outer loop (1 <= i < array.length), arr[i] is compared with all the previous elements arr[0] to arr[i-1] in the inner loop, suppose j is used in the inner loop. Then the steps are as given below-
- If(arr[i] > arr[j]) – that means arr[i] can extend the increasing subsequence ending at arr[j]
- Take the maximum of current known LIS ending at i and what we’d get by appending arr[i] to the LIS ending at j, as the value of dp[i].
Max value in the dp array is the length of the longest increasing subsequence.
public class LongestIncreasingSubsequence {
public static void main(String[] args) {
int[] arr = {10, 9, 2, 5, 3, 7, 1, 8};
System.out.println(Arrays.toString(arr));
System.out.println("lis "+ findLIS(arr));
}
// Using tabulation
public static int findLIS(int[] arr) {
int len = arr.length;
int[] dp = new int[len];
Arrays.fill(dp, 1);
int maxLis = 1;
for(int i = 1; i < len; i++) {
for(int j = 0; j < i; j++) {
if(arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// extract the length of LIS
for (int length : dp) {
maxLis = Math.max(maxLis, length);
}
return maxLis;
}
}
Output
[10, 9, 2, 5, 3, 7, 1, 8] lis 4
That's all for this topic Longest Increasing Subsequence Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment