Given an array arr[] consisting of N integers, the task is to find the maximum sum of a non-empty subsequence such that each pair of consecutive terms is of different parity (even or odd).
Examples:
Input: arr[] = {1, 2, 6, 8, -5, 10}
Output: 14
Explanation: Considering the subsequence {1, 8, -5, 10} which satisfies the given condition, sum of the subsequence = (1 + 8 – 5 + 10) = 14, which is the maximum possible sum.Input: arr[] = {1, -1, 1, -1}
Output: 1
Naive Approach: The simplest approach to solve the given problem is to generate all possible subsequences of the array and find the maximum sum of that subsequence having all adjacent elements of different parity.
Time Complexity: O(N*(2N))
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by using Dynamic Programming because it has overlapping subproblems and optimal substructure. The subproblems can be stored in dp[][] table using memoization where dp[i][prev] stores the maximum sum possible from the ith position to the end of the array when the parity of the previous number selected is ‘prev’. There are 2 cases for every state:
- Include the current element if parity differs from the previous element.
- Don’t include the current element.
A boolean variable is_selected is maintained to ensure that at least one number is selected from the array in the subsequence and then return the maximum out of the two cases in each recursive call. Follow the below steps to solve the problem:
- Define a recursive function maxSum(i, prev, is_selected) by performing the following steps:
- Check the base cases, if the value of i is equal to N, then return 0, or if the value of i is equal to N – 1 and is_selected is false, then return arr[i].
- If the result of the state dp[i][prev] is already computed, return this state dp[i][prev].
- If the parity of the current element is different from prev, then choose the current element as part of the subset and recursively call the maxSum function for the element at index (i + 1).
- Skip the current element for the current subset and recursively call the maxSum function for index (i + 1).
- Return the maximum value of the two cases from the current recursive calls.
- After completing the above steps, print the value of maxSum(0) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int dp[100][3];// Function to find the maximum sum of// subsequence with consecutive terms// having different parityint maxSum(int* arr, int i, int n, int prev, bool is_selected){ // Base Case if (i == n) { return 0; } // Store the parity of number at // the ith position int cur = abs(arr[i]) % 2; // If the dp state has already been // calculated, return it if (dp[i][prev] != -1) { return dp[i][prev]; } // If the array is traversed and // no element has been selected yet // then select the current element if (i == n - 1 && is_selected == 0) return dp[i][prev] = arr[i]; // If the parity of the current and // previously selected element are // different, then select the // current element if (cur != prev) { dp[i][prev] = arr[i] + maxSum(arr, i + 1, n, cur, 1); } // Skip the current element and move // to the next element dp[i][prev] = max(dp[i][prev], maxSum(arr, i + 1, n, prev, is_selected)); // Return the result return dp[i][prev];}// Function to calculate the maximum sum// subsequence with consecutive terms// having different parityvoid maxSumUtil(int arr[], int n){ // Initialize the dp[] array with -1 memset(dp, -1, sizeof(dp)); // Initially the prev value is set to // say 2, as the first element can // anyways be selected cout << maxSum(arr, 0, n, 2, 0);}// Driver Codeint main(){ int arr[] = { 1, 2, 6, 8, -5, 10 }; int N = sizeof(arr) / sizeof(arr[0]); maxSumUtil(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.Arrays;class GFG{// Function to find the maximum sum of// subsequence with consecutive terms// having different paritystatic int maxSum(int[] arr, int i, int n, int prev, boolean is_selected, int[][] dp){ // Base Case if (i == n) { return 0; } // Store the parity of number at // the ith position int cur = Math.abs(arr[i]) % 2; // If the dp state has already been // calculated, return it if (dp[i][prev] != -1) { return dp[i][prev]; } // If the array is traversed and // no element has been selected yet // then select the current element if (i == n - 1 && is_selected == false) return dp[i][prev] = arr[i]; // If the parity of the current and // previously selected element are // different, then select the // current element if (cur != prev) { dp[i][prev] = arr[i] + maxSum(arr, i + 1, n, cur, true, dp); } // Skip the current element and move // to the next element dp[i][prev] = Math.max(dp[i][prev], maxSum( arr, i + 1, n, prev, is_selected, dp)); // Return the result return dp[i][prev];}// Function to calculate the maximum sum// subsequence with consecutive terms// having different paritystatic void maxSumUtil(int arr[], int n){ int [][]dp = new int[100][3]; // Initialize the dp[] array with -1 for(int[] arr1 : dp) Arrays.fill(arr1, -1); // Initially the prev value is set to // say 2, as the first element can // anyways be selected System.out.print(maxSum(arr, 0, n, 2, false, dp));}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 2, 6, 8, -5, 10 }; int N = arr.length; maxSumUtil(arr, N);}}// This code is contributed by shreyasshetty788 |
Python3
# Python3 code for the above approach# Function to calculate the maximum sum# subsequence with consecutive terms# having different paritydef maxSum(arr, i, n, prev, is_selected, dp): # Base Case if(i == n): return 0 # Store the parity of number at # the ith position cur = abs(arr[i]) % 2 # If the dp state has already been # calculated, return it if (dp[i][prev] != -1): return dp[i][prev] # If the array is traversed and # no element has been selected yet # then select the current element if (i == n - 1 and is_selected == 0): dp[i][prev] = arr[i] return dp[i][prev] # If the parity of the current and # previously selected element are # different, then select the # current element if (cur != prev): dp[i][prev] = arr[i] + maxSum(arr, i + 1, n, cur, 1, dp) # Skip the current element and move # to the next element dp[i][prev] = max(dp[i][prev], maxSum( arr, i + 1, n, prev, is_selected, dp)) # Return the result return dp[i][prev]# Function to calculate the maximum sum# subsequence with consecutive terms# having different paritydef maxSumUtil(arr, n): dp = [[-1 for i in range(3)] for j in range(100)] print(maxSum(arr, 0, n, 2, 0, dp))# Driver Codeif __name__ == '__main__': arr = [ 1, 2, 6, 8, -5, 10 ] N = len(arr) maxSumUtil(arr, N) # This code is contributed by shreyasshetty788 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum sum of// subsequence with consecutive terms// having different paritystatic int maxSum(int []arr, int i, int n, int prev, bool is_selected, int [,]dp){ // Base Case if (i == n) { return 0; } // Store the parity of number at // the ith position int cur = Math.Abs(arr[i]) % 2; // If the dp state has already been // calculated, return it if (dp[i, prev] != -1) { return dp[i, prev]; } // If the array is traversed and // no element has been selected yet // then select the current element if (i == n - 1 && is_selected == false) return dp[i, prev] = arr[i]; // If the parity of the current and // previously selected element are // different, then select the // current element if (cur != prev) { dp[i, prev] = arr[i] + maxSum(arr, i + 1, n, cur, true, dp); } // Skip the current element and move // to the next element dp[i, prev] = Math.Max(dp[i, prev], maxSum( arr, i + 1, n, prev, is_selected, dp)); // Return the result return dp[i, prev];}// Function to calculate the maximum sum// subsequence with consecutive terms// having different paritystatic void maxSumUtil(int []arr, int n){ int [,]dp = new int[100, 3]; // Initialize the dp[] array with -1 for(int i = 0; i < 100; ++i) { for(int j = 0; j < 3; ++j) { dp[i, j] = -1; } } // Initially the prev value is set to // say 2, as the first element can // anyways be selected Console.Write(maxSum(arr, 0, n, 2, false, dp));}// Driver codepublic static void Main(String []args){ int []arr = { 1, 2, 6, 8, -5, 10 }; int N = arr.Length; maxSumUtil(arr, N);}}// This code is contributed by shreyasshetty788 |
Javascript
<script>// JavaScript program for the above approachlet dp = new Array(100).fill(0).map(() => new Array(3).fill(-1));// Function to find the maximum sum of// subsequence with consecutive terms// having different parityfunction maxSum(arr, i, n, prev, is_selected) { // Base Case if (i == n) { return 0; } // Store the parity of number at // the ith position let cur = Math.abs(arr[i]) % 2; // If the dp state has already been // calculated, return it if (dp[i][prev] != -1) { return dp[i][prev]; } // If the array is traversed and // no element has been selected yet // then select the current element if (i == n - 1 && is_selected == 0) return dp[i][prev] = arr[i]; // If the parity of the current and // previously selected element are // different, then select the // current element if (cur != prev) { dp[i][prev] = arr[i] + maxSum(arr, i + 1, n, cur, 1); } // Skip the current element and move // to the next element dp[i][prev] = Math.max(dp[i][prev], maxSum(arr, i + 1, n, prev, is_selected)); // Return the result return dp[i][prev];}// Function to calculate the maximum sum// subsequence with consecutive terms// having different parityfunction maxSumUtil(arr, n) { // Initially the prev value is set to // say 2, as the first element can // anyways be selected document.write(maxSum(arr, 0, n, 2, 0));}// Driver Codelet arr = [1, 2, 6, 8, -5, 10];let N = arr.lengthmaxSumUtil(arr, N);</script> |
Output:
14
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
