Longest alternating subsequence in terms of positive and negative integers | Java program to find the length of longest alternate subsequence ; LAS [ i ] [ pos ] array to find the length of LAS till index i by including or excluding element arr [ i ] on the basis of value of pos ; Base Case ; If current element is positive and pos is 1 Include the current element and change pos to 0 ; Recurr for the next iteration ; If current element is negative and pos is o Include the current element and change pos to 1 ; Recurr for the next iteration ; If current element is excluded , reccur for next iteration ; Driver 's Code ; Print LAS
class GFG { static int LAS [ ] [ ] = new int [ 1000 ] [ 2 ] ; static int solve ( int arr [ ] , int n , int i , int pos ) { if ( i == n ) return 0 ; if ( LAS [ i ] [ pos ] == 1 ) return LAS [ i ] [ pos ] ; int inc = 0 , exc = 0 ; if ( arr [ i ] > 0 && pos == 1 ) { pos = 0 ; inc = 1 + solve ( arr , n , i + 1 , pos ) ; } else if ( arr [ i ] < 0 && pos == 0 ) { pos = 1 ; inc = 1 + solve ( arr , n , i + 1 , pos ) ; } exc = solve ( arr , n , i + 1 , pos ) ; LAS [ i ] [ pos ] = Math . max ( inc , exc ) ; return LAS [ i ] [ pos ] ; } public static void main ( String [ ] args ) { int arr [ ] = { - 1 , 2 , 3 , 4 , 5 , - 6 , 8 , - 99 } ; int n = arr . length ; System . out . println ( Math . max ( solve ( arr , n , 0 , 0 ) , solve ( arr , n , 0 , 1 ) ) ) ; } }