To print the longest increasing subsequence

Solution:

import java.util.ArrayList;

import java.util.Arrays;

class Dsa {

    public static int lengthOfLIS() {

        int arr[]={5,4,11,1,16,8};

        int n=arr.length;

        int dp[]=new int[n];int hash[]=new int[n];

        Arrays.fill(dp,1);

        for(int i=1;i<n;i++)

        {

            hash[i]=i;

            for(int j=0;j<i;j++)

            {

                if(arr[i]>arr[j])

                {

                    if(dp[j]+1>dp[i])

                    {

                        dp[i]=dp[j]+1;

                        hash[i]=j;

                    }

                }

            }

        }

        int maxIdx=0;int lastIndex=-1;

        for(int i=0;i<n;i++)

        {

            if(dp[i]>dp[maxIdx])

            {

                maxIdx=i;

                //maxIdx=i;

                lastIndex=i;

            }

        }

        ArrayList<Integer> temp=new ArrayList<>();

    temp.add(arr[lastIndex]);

    

    while(hash[lastIndex] != lastIndex){ // till not reach the initialization value

        lastIndex = hash[lastIndex];

        temp.add(arr[lastIndex]);    

    }

    

    // reverse the array 

    

    System.out.print("The subsequence elements are ");

    

    for(int i=temp.size()-1; i>=0; i--){

        System.out.print(temp.get(i)+" ");

    }

    System.out.println();

        return dp[maxIdx];

    }

    public static void main(String[] args) {

        lengthOfLIS();

    }

}