Maximum Sum Subsequence made up of consecutive elements of different parity

0 0 7 minutes read

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*(2^N))
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 parity
int 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 parity
void 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 Code
int 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 approach
import java.io.*;
import java.util.Arrays;
 
class GFG{
 
// Function to find the maximum sum of
// subsequence with consecutive terms
// having different parity
static 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 parity
static 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 Code
public 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 parity
def 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 parity
def maxSumUtil(arr, n):
     
    dp = [[-1 for i in range(3)] 
              for j in range(100)]
               
    print(maxSum(arr, 0, n, 2, 0, dp))
 
# Driver Code
if __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 approach
using System;
 
class GFG{
     
// Function to find the maximum sum of
// subsequence with consecutive terms
// having different parity
static 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 parity
static 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 code
public 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 approach
 
 
let 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 parity
function 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 parity
function 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 Code
let arr = [1, 2, 6, 8, -5, 10];
let N = arr.length
maxSumUtil(arr, N);
 
</script>

Output:

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 zambiatek!