Maximum Sum Subsequence made up of consecutive elements of different parity | JavaScript program for the above approach ; Function to find the maximum sum of subsequence with consecutive terms having different parity ; Base Case ; Store the parity of number at the ith position ; If the dp state has already been calculated , return it ; If the array is traversed and no element has been selected yet then select the current element ; If the parity of the current and previously selected element are different , then select the current element ; Skip the current element and move to the next element ; Return the result ; Function to calculate the maximum sum subsequence with consecutive terms having different parity ; Initially the prev value is set to say 2 , as the first element can anyways be selected ; Driver Code
let dp = new Array ( 100 ) . fill ( 0 ) . map ( ( ) => new Array ( 3 ) . fill ( - 1 ) ) ; function maxSum ( arr , i , n , prev , is_selected ) { if ( i == n ) { return 0 ; } let cur = Math . abs ( arr [ i ] ) % 2 ; if ( dp [ i ] [ prev ] != - 1 ) { return dp [ i ] [ prev ] ; } if ( i == n - 1 && is_selected == 0 ) return dp [ i ] [ prev ] = arr [ i ] ; if ( cur != prev ) { dp [ i ] [ prev ] = arr [ i ] + maxSum ( arr , i + 1 , n , cur , 1 ) ; } dp [ i ] [ prev ] = Math . max ( dp [ i ] [ prev ] , maxSum ( arr , i + 1 , n , prev , is_selected ) ) ; return dp [ i ] [ prev ] ; } function maxSumUtil ( arr , n ) { document . write ( maxSum ( arr , 0 , n , 2 , 0 ) ) ; } let arr = [ 1 , 2 , 6 , 8 , - 5 , 10 ] ; let N = arr . length maxSumUtil ( arr , N ) ;