Maximum Sum Subsequence made up of consecutive elements of different parity | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 100 ] [ 3 ] ; int maxSum ( int * arr , int i , int n , int prev , bool is_selected ) { if ( i == n ) { return 0 ; } int cur = 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 ] = max ( dp [ i ] [ prev ] , maxSum ( arr , i + 1 , n , prev , is_selected ) ) ; return dp [ i ] [ prev ] ; } void maxSumUtil ( int arr [ ] , int n ) { memset ( dp , -1 , sizeof ( dp ) ) ; cout << maxSum ( arr , 0 , n , 2 , 0 ) ; } int main ( ) { int arr [ ] = { 1 , 2 , 6 , 8 , -5 , 10 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maxSumUtil ( arr , N ) ; return 0 ; }