Maximum Sum Subsequence made up of consecutive elements of different parity | Function to calculate the maximum sum 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 ; Initialize the dp [ ] array with - 1 ; Initially the prev value is set to say 2 , as the first element can anyways be selected ; Driver Code
def maxSum ( arr , i , n , prev , is_selected , dp ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT cur = abs ( arr [ i ] ) % 2 NEW_LINE if ( dp [ i ] [ prev ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ prev ] NEW_LINE DEDENT if ( i == n - 1 and is_selected == 0 ) : NEW_LINE INDENT dp [ i ] [ prev ] = arr [ i ] NEW_LINE return dp [ i ] [ prev ] NEW_LINE DEDENT if ( cur != prev ) : NEW_LINE INDENT dp [ i ] [ prev ] = arr [ i ] + maxSum ( arr , i + 1 , n , cur , 1 , dp ) NEW_LINE DEDENT dp [ i ] [ prev ] = max ( dp [ i ] [ prev ] , maxSum ( arr , i + 1 , n , prev , is_selected , dp ) ) NEW_LINE return dp [ i ] [ prev ] NEW_LINE DEDENT def maxSumUtil ( arr , n ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( 3 ) ] for j in range ( 100 ) ] NEW_LINE print ( maxSum ( arr , 0 , n , 2 , 0 , dp ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 6 , 8 , - 5 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE maxSumUtil ( arr , N ) NEW_LINE DEDENT