Maximum even sum subsequence of length K
Given an array arr[] consisting of N positive integers, and an integer K, the task is to find the maximum possible even sum of any subsequence of size K. If it is not possible to find any even sum subsequence of size K, then print -1.
Examples:
Input: arr[] ={4, 2, 6, 7, 8}, K = 3
Output: 18
Explanation: Subsequence having maximum even sum of size K( = 3 ) is {4, 6, 8}.
Therefore, the required output is 4 + 6 + 8 = 18.Input: arr[] = {5, 5, 1, 1, 3}, K = 3
Output: -1
Naive Approach: The simplest approach to solve this problem to generate all possible subsequences of size K from the given array and print the value of the maximum possible even sum the possible subsequences of the given array.
Time Complexity: O(K * NK)
Auxiliary Space: O(K)
Efficient Approach: To optimize the above approach the idea is to store all even and odd numbers of the given array into two separate arrays and sort both these arrays. Finally, use the Greedy technique to calculate the maximum sum even subsequence of size K. Follow the steps below to solve the problem:
- Initialize a variable, say maxSum to store the maximum even sum of a subsequence of the given array.
- Initialize two arrays, say Even[] and Odd[] to store all the even numbers and odd numbers of the given array respectively.
- Traverse the given array and store all the even numbers and odd numbers of the given array into Even[] and Odd[] array respectively.
- Sort Even[] and Odd[] arrays.
- Initialize two variables, say i and j to store the index of Even[] and Odd[] array respectively.
- Traverse Even[], Odd[] arrays and check the following conditions:
- If K % 2 == 1 then increment the value of maxSum by Even[i].
- Otherwise, increment the value of maxSum by max(Even[i] + Even[i – 1], Odd[j] + Odd[j – 1]).
- Finally, print the value of maxSum.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find the // maximum even sum of any // subsequence of length K int evenSumK( int arr[], int N, int K) { // If count of elements // is less than K if (K > N) { return -1; } // Stores maximum // even subsequence sum int maxSum = 0; // Stores Even numbers vector< int > Even; // Stores Odd numbers vector< int > Odd; // Traverse the array for ( int i = 0; i < N; i++) { // If current element // is an odd number if (arr[i] % 2) { // Insert odd number Odd.push_back(arr[i]); } else { // Insert even numbers Even.push_back(arr[i]); } } // Sort Odd[] array sort(Odd.begin(), Odd.end()); // Sort Even[] array sort(Even.begin(), Even.end()); // Stores current index // Of Even[] array int i = Even.size() - 1; // Stores current index // Of Odd[] array int j = Odd.size() - 1; while (K > 0) { // If K is odd if (K % 2 == 1) { // If count of elements // in Even[] >= 1 if (i >= 0) { // Update maxSum maxSum += Even[i]; // Update i i--; } // If count of elements // in Even[] array is 0. else { return -1; } // Update K K--; } // If count of elements // in Even[] and odd[] >= 2 else if (i >= 1 && j >= 1) { if (Even[i] + Even[i - 1] <= Odd[j] + Odd[j - 1]) { // Update maxSum maxSum += Odd[j] + Odd[j - 1]; // Update j. j -= 2; } else { // Update maxSum maxSum += Even[i] + Even[i - 1]; // Update i i -= 2; } // Update K K -= 2; } // If count of elements // in Even[] array >= 2. else if (i >= 1) { // Update maxSum maxSum += Even[i] + Even[i - 1]; // Update i. i -= 2; // Update K. K -= 2; } // If count of elements // in Odd[] array >= 1 else if (j >= 1) { // Update maxSum maxSum += Odd[j] + Odd[j - 1]; // Update i. j -= 2; // Update K. K -= 2; } else { return -1; } } return maxSum; } // Driver Code int main() { int arr[] = { 2, 4, 10, 3, 5 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 3; cout << evenSumK(arr, N, K); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to find the // maximum even sum of any // subsequence of length K static int evenSumK( int arr[], int N, int K) { // If count of elements // is less than K if (K > N) { return - 1 ; } // Stores maximum even // subsequence sum int maxSum = 0 ; // Stores Even numbers ArrayList<Integer> Even = new ArrayList<Integer>(); // Stores Odd numbers ArrayList<Integer> Odd = new ArrayList<Integer>(); // Traverse the array for ( int i = 0 ; i < N; i++) { // If current element // is an odd number if (arr[i] % 2 == 1 ) { // Insert odd number Odd.add(arr[i]); } else { // Insert even numbers Even.add(arr[i]); } } // Sort Odd[] array Collections.sort(Odd); // Sort Even[] array Collections.sort(Even); // Stores current index // Of Even[] array int i = Even.size() - 1 ; // Stores current index // Of Odd[] array int j = Odd.size() - 1 ; while (K > 0 ) { // If K is odd if (K % 2 == 1 ) { // If count of elements // in Even[] >= 1 if (i >= 0 ) { // Update maxSum maxSum += Even.get(i); // Update i i--; } // If count of elements // in Even[] array is 0. else { return - 1 ; } // Update K K--; } // If count of elements // in Even[] and odd[] >= 2 else if (i >= 1 && j >= 1 ) { if (Even.get(i) + Even.get(i - 1 ) <= Odd.get(j) + Odd.get(j - 1 )) { // Update maxSum maxSum += Odd.get(j) + Odd.get(j - 1 ); // Update j j -= 2 ; } else { // Update maxSum maxSum += Even.get(i) + Even.get(i - 1 ); // Update i i -= 2 ; } // Update K K -= 2 ; } // If count of elements // in Even[] array >= 2. else if (i >= 1 ) { // Update maxSum maxSum += Even.get(i) + Even.get(i - 1 ); // Update i i -= 2 ; // Update K K -= 2 ; } // If count of elements // in Odd[] array >= 1 else if (j >= 1 ) { // Update maxSum maxSum += Odd.get(j) + Odd.get(j - 1 ); // Update i. j -= 2 ; // Update K. K -= 2 ; } else return - 1 ; } return maxSum; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 4 , 10 , 3 , 5 }; int N = arr.length; int K = 3 ; System.out.println(evenSumK(arr, N, K)); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to find the # maximum even sum of any # subsequence of length K def evenSumK(arr, N, K): # If count of elements # is less than K if (K > N): return - 1 # Stores maximum # even subsequence sum maxSum = 0 # Stores Even numbers Even = [] # Stores Odd numbers Odd = [] # Traverse the array for i in range (N): # If current element # is an odd number if (arr[i] % 2 ): # Insert odd number Odd.append(arr[i]) else : # Insert even numbers Even.append(arr[i]) # Sort Odd[] array Odd.sort(reverse = False ) # Sort Even[] array Even.sort(reverse = False ) # Stores current index # Of Even[] array i = len (Even) - 1 # Stores current index # Of Odd[] array j = len (Odd) - 1 while (K > 0 ): # If K is odd if (K % 2 = = 1 ): # If count of elements # in Even[] >= 1 if (i > = 0 ): # Update maxSum maxSum + = Even[i] # Update i i - = 1 # If count of elements # in Even[] array is 0. else : return - 1 # Update K K - = 1 # If count of elements # in Even[] and odd[] >= 2 elif (i > = 1 and j > = 1 ): if (Even[i] + Even[i - 1 ] < = Odd[j] + Odd[j - 1 ]): # Update maxSum maxSum + = Odd[j] + Odd[j - 1 ] # Update j. j - = 2 else : # Update maxSum maxSum + = Even[i] + Even[i - 1 ] # Update i i - = 2 # Update K K - = 2 # If count of elements # in Even[] array >= 2. elif (i > = 1 ): # Update maxSum maxSum + = Even[i] + Even[i - 1 ] # Update i. i - = 2 # Update K. K - = 2 # If count of elements # in Odd[] array >= 2 elif (j > = 1 ): # Update maxSum maxSum + = Odd[j] + Odd[j - 1 ] # Update i. j - = 2 # Update K. K - = 2 else : return - 1 ; return maxSum # Driver Code if __name__ = = '__main__' : arr = [ 2 , 4 , 9 ] N = len (arr) K = 3 print (evenSumK(arr, N, K)) # This code is contributed by ipg2016107 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to find the // maximum even sum of any // subsequence of length K static int evenSumK( int [] arr, int N, int K) { // If count of elements // is less than K if (K > N) { return -1; } // Stores maximum even // subsequence sum int maxSum = 0; // Stores Even numbers List< int > Even = new List< int >(); // Stores Odd numbers List< int > Odd = new List< int >(); // Traverse the array for ( int l = 0; l < N; l++) { // If current element // is an odd number if (arr[l] % 2 == 1) { // Insert odd number Odd.Add(arr[l]); } else { // Insert even numbers Even.Add(arr[l]); } } // Sort Odd[] array Odd.Sort(); // Sort Even[] array Even.Sort(); // Stores current index // Of Even[] array int i = Even.Count - 1; // Stores current index // Of Odd[] array int j = Odd.Count - 1; while (K > 0) { // If K is odd if (K % 2 == 1) { // If count of elements // in Even[] >= 1 if (i >= 0) { // Update maxSum maxSum += Even[i]; // Update i i--; } // If count of elements // in Even[] array is 0. else { return -1; } // Update K K--; } // If count of elements // in Even[] and odd[] >= 2 else if (i >= 1 && j >= 1) { if (Even[i] + Even[i - 1] <= Odd[j] + Odd[j - 1]) { // Update maxSum maxSum += Odd[j] + Odd[j - 1]; // Update j j -= 2; } else { // Update maxSum maxSum += Even[i] + Even[i - 1]; // Update i i -= 2; } // Update K K -= 2; } // If count of elements // in Even[] array >= 2. else if (i >= 1) { // Update maxSum maxSum += Even[i] + Even[i - 1]; // Update i i -= 2; // Update K K -= 2; } // If count of elements // in Odd[] array >= 2 else if (j >= 1) { // Update maxSum maxSum += Odd[j] + Odd[j - 1]; // Update i. j -= 2; // Update K. K -= 2; } else return -1; } return maxSum; } // Driver code public static void Main(String[] args) { int [] arr = { 2, 4, 10, 3, 5 }; int N = arr.Length; int K = 3; Console.WriteLine(evenSumK(arr, N, K)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the // maximum even sum of any // subsequence of length K function evenSumK(arr, N, K) { // If count of elements // is less than K if (K > N) { return -1; } // Stores maximum // even subsequence sum var maxSum = 0; // Stores Even numbers var Even = []; // Stores Odd numbers var Odd = []; // Traverse the array for ( var i = 0; i < N; i++) { // If current element // is an odd number if (arr[i] % 2) { // Insert odd number Odd.push(arr[i]); } else { // Insert even numbers Even.push(arr[i]); } } // Sort Odd[] array Odd.sort((a,b)=> a-b); Even.sort((a,b)=> a-b); // Stores current index // Of Even[] array var i = Even.length - 1; // Stores current index // Of Odd[] array var j = Odd.length - 1; while (K > 0) { // If K is odd if (K % 2 == 1) { // If count of elements // in Even[] >= 1 if (i >= 0) { // Update maxSum maxSum += Even[i]; // Update i i--; } // If count of elements // in Even[] array is 0. else { return -1; } // Update K K--; } // If count of elements // in Even[] and odd[] >= 2 else if (i >= 1 && j >= 1) { if (Even[i] + Even[i - 1] <= Odd[j] + Odd[j - 1]) { // Update maxSum maxSum += Odd[j] + Odd[j - 1]; // Update j. j -= 2; } else { // Update maxSum maxSum += Even[i] + Even[i - 1]; // Update i i -= 2; } // Update K K -= 2; } // If count of elements // in Even[] array >= 2. else if (i >= 1) { // Update maxSum maxSum += Even[i] + Even[i - 1]; // Update i. i -= 2; // Update K. K -= 2; } // If count of elements // in Odd[] array >= 1 else if (j >= 1) { // Update maxSum maxSum += Odd[j] + Odd[j - 1]; // Update i. j -= 2; // Update K. K -= 2; } else return -1; } return maxSum; } // Driver Code var arr = [2, 4, 10, 3, 5]; var N = arr.length; var K = 3; document.write( evenSumK(arr, N, K)); </script> |
18
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Contact Us