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 [ ] [ ] ; Initialize dp [ ] [ ] ; Function Call ; Given array arr [ ] ; Function call
function findMax ( a , dp , i , flag ) { if ( i == a . length ) { return 0 ; } if ( dp [ i ] [ flag ] != - 1 ) { return dp [ i ] [ flag ] ; } let ans ; if ( flag == 0 ) { ans = Math . max ( findMax ( a , dp , i + 1 , 0 ) , a [ i ] + findMax ( a , dp , i + 1 , 1 ) ) ; } else { ans = Math . max ( findMax ( a , dp , i + 1 , 1 ) , - 1 * a [ i ] + findMax ( a , dp , i + 1 , 0 ) ) ; } return dp [ i ] [ flag ] = ans ; } function findMaxSumUtil ( arr , N ) { let dp = new Array ( N ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j < 2 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( findMax ( arr , dp , 0 , 0 ) ) ; } let arr = [ 1 , 2 , 3 , 4 , 1 , 2 ] ; let N = arr . length ; findMaxSumUtil ( arr , N ) ;