Longest alternating subsequence in terms of positive and negative integers | Python3 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
import numpy as np NEW_LINE LAS = np . zeros ( ( 1000 , 2 ) ) NEW_LINE for i in range ( 1000 ) : NEW_LINE INDENT for j in range ( 2 ) : NEW_LINE INDENT LAS [ i ] [ j ] = False NEW_LINE DEDENT DEDENT def solve ( arr , n , i , pos ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( LAS [ i ] [ pos ] ) : NEW_LINE INDENT return LAS [ i ] [ pos ] ; NEW_LINE DEDENT inc = 0 ; exc = 0 ; NEW_LINE if ( arr [ i ] > 0 and pos == True ) : NEW_LINE INDENT pos = False ; NEW_LINE inc = 1 + solve ( arr , n , i + 1 , pos ) ; NEW_LINE DEDENT elif ( arr [ i ] < 0 and pos == False ) : NEW_LINE INDENT pos = True ; NEW_LINE inc = 1 + solve ( arr , n , i + 1 , pos ) ; NEW_LINE DEDENT exc = solve ( arr , n , i + 1 , pos ) ; NEW_LINE LAS [ i ] [ pos ] = max ( inc , exc ) ; NEW_LINE return LAS [ i ] [ pos ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ - 1 , 2 , 3 , 4 , 5 , - 6 , 8 , - 99 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( max ( solve ( arr , n , 0 , 0 ) , solve ( arr , n , 0 , 1 ) ) ) ; NEW_LINE DEDENT