Q9 PepCoding | Print All Longest Increasing Subsequences

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    
    public static class Pair {
        int l;  //length
        int i;  //index
        int v;  //value
        String psf;
        
        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 []nums){
           /* 1D array
        storage- every cell denotes LIS till that cell ,mandatory that LIS ends at 
        that cell

        moving fromt left to right(small problem to large problem)
        */

        int n = nums.length;

        //base case
        // if(n == 1)return 1;
        int dp[] = new int[n];
        dp[0] = 1;  //LIS for 1 length will be of length 1 
        
        int ans = 1;
        for(int i = 1 ; i < n ; i++){

/*finding max LIS in previous elements in dp and also ensuring that current element
is greater than last element of previous LIS , as we have already assigned storage 
ensuring that LIS will end at that element so we already know that last element will 
be previous element only  */


            for(int j = i-1 ; j >=0 ; j--){
                
//for printing we are also taking equal values and not strictly
//greater values 
                if(nums[j] <= nums[i])
                dp[i] = Math.max(dp[i], dp[j]);
            }
            dp[i] += 1;

            ans = Math.max(dp[i] , ans);
        }        
        
/*we are returning ans and not dp[n-1] as dp[n-1] will just store LIS which the and 
will end at arr[n-1] but we need maximum length so we will store max as we traverse 
put in values in dp */

//now printing our answers through BFS for which we need pair class
        
        
        BFS(dp , ans , nums);

    }
    
    public static void BFS(int dp[] , int ans , int nums[]){
        
        ArrayDeque<Pair> q= new ArrayDeque<>();
        
        //add all elements which "ans" length stored in dp
        
        for(int i = 0 ; i < dp.length ; i++)
        if(dp[i]==ans)
        q.add(new Pair(dp[i],i,nums[i],nums[i]+""));
        
        
        //now remove print add children
        while(q.size()>0){
            Pair rem = q.removeFirst();
            
            int length = rem.l , idx = rem.i , val = rem.v;
            String psf = rem.psf;
            
            //if we got to LIS with 1 length print psf
            if(length ==1)
            System.out.println(psf);
            
//adding all children of rem which have length -1 and are smaller
            
            for(int j = 0 ; j < idx ; j++){
                
                if(dp[j]== length - 1 && nums[j] <= val)
                q.add(new Pair(dp[j],j,nums[j],nums[j]+" -> "+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 < n ; i++){
            arr[i] = scn.nextInt();
        }

        solution(arr);

        scn.close();
    }
}