Maximum Sum Subsequence made up of consecutive elements of different parity | Java 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 ; 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
import java . io . * ; import java . util . Arrays ; class GFG { static int maxSum ( int [ ] arr , int i , int n , int prev , boolean is_selected , int [ ] [ ] dp ) { if ( i == n ) { return 0 ; } int cur = Math . abs ( arr [ i ] ) % 2 ; if ( dp [ i ] [ prev ] != - 1 ) { return dp [ i ] [ prev ] ; } if ( i == n - 1 && is_selected == false ) return dp [ i ] [ prev ] = arr [ i ] ; if ( cur != prev ) { dp [ i ] [ prev ] = arr [ i ] + maxSum ( arr , i + 1 , n , cur , true , dp ) ; } dp [ i ] [ prev ] = Math . max ( dp [ i ] [ prev ] , maxSum ( arr , i + 1 , n , prev , is_selected , dp ) ) ; return dp [ i ] [ prev ] ; } static void maxSumUtil ( int arr [ ] , int n ) { int [ ] [ ] dp = new int [ 100 ] [ 3 ] ; for ( int [ ] arr1 : dp ) Arrays . fill ( arr1 , - 1 ) ; System . out . print ( maxSum ( arr , 0 , n , 2 , false , dp ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 6 , 8 , - 5 , 10 } ; int N = arr . length ; maxSumUtil ( arr , N ) ; } }