Number of Longest Increasing Subsequences | Java program for the above approach ; Function to count the number of LIS in the array nums [ ] ; Base Case ; Initialize dp_l array with 1 s ; Initialize dp_c array with 1 s ; If current element is smaller ; Store the maximum element from dp_l ; Stores the count of LIS ; Traverse dp_l and dp_c simultaneously ; Update the count ; Return the count of LIS ; Driver code ; Given array arr [ ] ; Function Call
import java . util . * ; class GFG { static int findNumberOfLIS ( int [ ] nums ) { if ( nums . length == 0 ) return 0 ; int n = nums . length ; int [ ] dp_l = new int [ n ] ; Arrays . fill ( dp_l , 1 ) ; int [ ] dp_c = new int [ n ] ; Arrays . fill ( dp_c , 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( nums [ i ] <= nums [ j ] ) continue ; if ( dp_l [ j ] + 1 > dp_l [ i ] ) { dp_l [ i ] = dp_l [ j ] + 1 ; dp_c [ i ] = dp_c [ j ] ; } else if ( dp_l [ j ] + 1 == dp_l [ i ] ) dp_c [ i ] += dp_c [ j ] ; } } int max_length = 0 ; for ( int i : dp_l ) max_length = Math . max ( i , max_length ) ; int count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( dp_l [ i ] == max_length ) count += dp_c [ i ] ; } return count ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 3 , 5 , 4 , 7 } ; System . out . print ( findNumberOfLIS ( arr ) + "NEW_LINE"); } }