Longest alternating subsequence in terms of positive and negative integers | C ++ 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 true Include the current element and change pos to false ; Recurr for the next iteration ; If current element is negative and pos is false Include the current element and change pos to true ; Recurr for the next iteration ; If current element is excluded , reccur for next iteration ; Driver 's Code ; Print LAS
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LAS [ 1000 ] [ 2 ] = { false } ; int solve ( int arr [ ] , int n , int i , bool pos ) { if ( i == n ) return 0 ; if ( LAS [ i ] [ pos ] ) return LAS [ i ] [ pos ] ; int inc = 0 , exc = 0 ; if ( arr [ i ] > 0 && pos == true ) { pos = false ; inc = 1 + solve ( arr , n , i + 1 , pos ) ; } else if ( arr [ i ] < 0 && pos == false ) { pos = true ; inc = 1 + solve ( arr , n , i + 1 , pos ) ; } exc = solve ( arr , n , i + 1 , pos ) ; LAS [ i ] [ pos ] = max ( inc , exc ) ; return LAS [ i ] [ pos ] ; } int main ( ) { int arr [ ] = { -1 , 2 , 3 , 4 , 5 , -6 , 8 , -99 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << max ( solve ( arr , n , 0 , 0 ) , solve ( arr , n , 0 , 1 ) ) ; }