Redirecting to
NADOS


  Prev   Next

PRINT ALL LONGEST INCREASING SUBSEQUENCES







Life doesn't get easier or more forgiving, we get stronger and more resilient.

PRINT ALL LONGEST INCREASING SUBSEQUENCES

Welcome coder

Hey coder. Ready to begin with the question, "Print All Longest Increasing Subsequences"?

Important Link : Problem Link, Question Vedio,Solution Video Link

Wait, before moving further go through the outline of the problem.

Understanding The Problem
  • You are given a number N representing the number of elements.
  • You are given N space separated numbers.
  • Your task is to find & amp; print:
    1. Length of & quot;Longest Increasing Subsequence& quot;.
    2. All & quot;Longest Increasing Subsequence(s)& quot;.

Let the input array be [10, 22, 9, 33, 21, 50, 41, 60, 80, 3 ].

The longest increasing subsequences for this input are [10, 22, 33, 50, 60, 80] and [10, 22, 33, 41, 40, 80]. They are both of length 6.

We have already discussed how to find the LIS previously.

Approach

We quickly make the LIS table for the given input.

img

We find that the longest length is 6.

Now using the reverse method, we apply Breadth First Search as shown in figure

img
  • Here, in x-y, x denotes the length of the subsequence and y denotes the corresponding element.
  • we put the element 80 with the longest length, 6 in a queue.
  • On applying Breadth First Search, the element 80 is removed.
  • Then the element from which the subsequence of 80 was made, i.e. the element with length 5, is added to the queue.
  • Hence, the element 60 of length 5 is added to the queue.
  • Had there been multiple elements of length=5, then they all would have been added to the queue.
  • Again, we remove 5-60 from the queue and add all the elements of length 4 which are less than the value 60 in the queue. Hence, 4-41 and 4-50 are added to the queue.
  • This process is continued for lengths 3, 2 and 1 as seen in figure 2.
  • Hence, we obtain our desired answers, [10, 22, 33, 50, 60, 80] and [10, 22, 33, 41, 40, 80].

Now that we have shown you to process for one input, we want you to print all the longest Increasing subsequences for the input [10, 22, 9, 33, 21, 50, 41, 60, 80, 3].

When you have attempted it yourself, we want you to go watch the solution video to tally your result.

HOW

We are now going to code this program. We are sure you will find this code quite simple since we have already learnt to code LIS in the previous problems.

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Queue; import java.util.Scanner; public class Main{ public static class Pair { //1 int l; //l=length int i; //i=index int v; //v=value String psf; //psf=path so far Pair(int l, int i, int v, String psf){ this.l = l; this.i = i; this.v = v; this.psf = psf; } } public static void solution(int []arr){ int[]dp=new int[arr.length]; //1 int omax=0; //omax= overall max int omi=0; //omi=overall max index for(int i=0;i & lt;dp.length;i++){ //2 int max=0; for(int j=0;j & lt;i;j++){ if(arr[j]& lt;=arr[i]){ if(dp[j]& gt;max){ max=dp[j]; } } } dp[i]=max+1; if(dp[i]& gt;omax){ omax=dp[i]; omi=i; } } System.out.println(omax); ArrayDeque& lt;Pair& gt; queue=new ArrayDeque& lt;& gt;(); //3 queue.add(new Pair(omax,omi,arr[omi],arr[omi]+& quot;& quot;)); while(queue.size()& gt;0){ //4 Pair rem=queue.removeFirst(); if(rem.l==1){ //5 System.out.println(rem.psf); } for(int j=rem.i-1;j& gt;=0;j--){ //6 if(dp[j]==rem.l-1 & amp;& amp; arr[j]& lt;=rem.v){ queue.add(new Pair(dp[j],j,arr[j],arr[j]+&q uot; -& gt; & quot;+rem.psf)); } } } } public static void main(String []args){ Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int arr[] = new int[n]; for(int i = 0 ; i & lt; n ; i++){ arr[i] = scn.nextInt(); } solution(arr); scn.close(); } }
java; true";
  1. We make a class "Pair" which has data members length, index, value and path so far.
  2. As already discussed in the previous questions, we find the LIS and print the maximum length of the increasing subsequence.
  3. Now we make a queue and add the element of longest subsequence in the queue.
  4. While the queue is non-empty, we remove the first element of the queue.
  5. If the length of the removed Pair is 1, then we print its path so far.
  6. Else, we apply a loop from the next largest length to the 0 and add those Pairs in the queue whose length is 1 less than the removed element and the value is less than the value of the removed element.
TIME COMPLEXITY:
SPACE COMPLEXITY : O(n2)

With this, we come to the end of our discussion. We hope it was enjoyable.

If you still have any difficulties in the solution, we suggest you watch its solution video.

All the best for an exciting future!
Happy Coding!

Print All Longest Increasing Subsequences
Author: Shreeya Gupta
 
Run
Id Name