Construction of Longest Increasing Subsequence ( LIS ) and printing LIS sequence | Dynamic Programming solution to conLongest Increasing Subsequence ; Utility function to print LIS ; Function to conand print Longest Increasing Subsequence ; L [ i ] - The longest increasing sub - sequence ends with arr [ i ] ; L [ 0 ] is equal to arr [ 0 ] ; Start from index 1 ; Do for every j less than i ; L [ i ] = { Max ( L [ j ] ) } + arr [ i ] where j < i and arr [ j ] < arr [ i ] ; L [ i ] ends with arr [ i ] ; L [ i ] now stores increasing sub - sequence of arr [ 0. . i ] that ends with arr [ i ] ; LIS will be max of all increasing sub - sequences of arr ; max will contain LIS ; Driver function ; construct and print LIS of arr
import java . util . * ; class GFG { static void printLIS ( Vector < Integer > arr ) { for ( int x : arr ) System . out . print ( x + " ▁ " ) ; System . out . println ( ) ; } static void constructPrintLIS ( int arr [ ] , int n ) { Vector < Integer > L [ ] = new Vector [ n ] ; for ( int i = 0 ; i < L . length ; i ++ ) L [ i ] = new Vector < Integer > ( ) ; L [ 0 ] . add ( arr [ 0 ] ) ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ i ] > arr [ j ] ) && ( L [ i ] . size ( ) < L [ j ] . size ( ) + 1 ) ) L [ i ] = L [ j ] ; } L [ i ] . add ( arr [ i ] ) ; } Vector < Integer > max = L [ 0 ] ; for ( Vector < Integer > x : L ) if ( x . size ( ) > max . size ( ) ) max = x ; printLIS ( max ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 2 , 4 , 5 , 1 } ; int n = arr . length ; constructPrintLIS ( arr , n ) ; } }