Maximize count of Decreasing Consecutive Subsequences from an Array | Java program to implement the above approach ; Function to find the maximum number number of required subsequences ; HashMap to store number of arrows available with height of arrow as key ; Stores the maximum count of possible subsequences ; Stores the count of possible subsequences ; Check if i - th element can be part of any of the previous subsequence ; Count of subsequences possible with arr [ i ] as the next element ; If more than one such subsequence exists ; Include arr [ i ] in a subsequence ; Otherwise ; Increase count of subsequence possible with arr [ i ] - 1 as the next element ; Start a new subsequence ; Increase count of subsequence possible with arr [ i ] - 1 as the next element ; Return the answer ; Driver Code
import java . util . * ; class GFG { static int maxSubsequences ( int arr [ ] , int n ) { HashMap < Integer , Integer > map = new HashMap < > ( ) ; int maxCount = 0 ; int count ; for ( int i = 0 ; i < n ; i ++ ) { if ( map . containsKey ( arr [ i ] ) ) { count = map . get ( arr [ i ] ) ; if ( count > 1 ) { map . put ( arr [ i ] , count - 1 ) ; } else map . remove ( arr [ i ] ) ; if ( arr [ i ] - 1 > 0 ) map . put ( arr [ i ] - 1 , map . getOrDefault ( arr [ i ] - 1 , 0 ) + 1 ) ; } else { maxCount ++ ; if ( arr [ i ] - 1 > 0 ) map . put ( arr [ i ] - 1 , map . getOrDefault ( arr [ i ] - 1 , 0 ) + 1 ) ; } } return maxCount ; } public static void main ( String [ ] args ) { int n = 5 ; int arr [ ] = { 4 , 5 , 2 , 1 , 4 } ; System . out . println ( maxSubsequences ( arr , n ) ) ; } }