Maximum sum possible by assigning alternate positive and negative sign to elements in a subsequence | Function to find the maximum sum subsequence ; Base Case ; If current state is already calculated then use it ; If current element is positive ; Update ans and recursively call with update value of flag ; Else current element is negative ; Update ans and recursively call with update value of flag ; Return maximum sum subsequence ; Function that finds the maximum sum of element of the subsequence with alternate + ve and - ve signs ; Create auxiliary array dp [ ] [ ] ; Function call ; Driver Code ; Given array arr [ ] ; Function call
def findMax ( a , dp , i , flag ) : NEW_LINE INDENT if ( i == len ( a ) ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ flag ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ flag ] NEW_LINE DEDENT ans = 0 NEW_LINE if ( flag == 0 ) : NEW_LINE INDENT ans = max ( findMax ( a , dp , i + 1 , 0 ) , a [ i ] + findMax ( a , dp , i + 1 , 1 ) ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = max ( findMax ( a , dp , i + 1 , 1 ) , - 1 * a [ i ] + findMax ( a , dp , i + 1 , 0 ) ) NEW_LINE DEDENT dp [ i ] [ flag ] = ans NEW_LINE return ans NEW_LINE DEDENT def findMaxSumUtil ( arr , N ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( 2 ) ] for i in range ( N ) ] NEW_LINE print ( findMax ( arr , dp , 0 , 0 ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 1 , 2 ] NEW_LINE N = len ( arr ) NEW_LINE findMaxSumUtil ( arr , N ) NEW_LINE DEDENT