Dada una array arr[] que consta de N enteros positivos y un entero K , la tarea es encontrar la suma par máxima posible de cualquier subsecuencia de tamaño K . Si no es posible encontrar ninguna subsecuencia de suma par de tamaño K , imprima -1 .
Ejemplos:
Entrada: arr[] ={4, 2, 6, 7, 8}, K = 3
Salida: 18
Explicación: La subsecuencia que tiene una suma par máxima de tamaño K( = 3 ) es {4, 6, 8}.
Por lo tanto, la salida requerida es 4 + 6 + 8 = 18.Entrada: arr[] = {5, 5, 1, 1, 3}, K = 3
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las posibles subsecuencias de tamaño K a partir de la array dada e imprimir el valor del máximo posible, incluso sumar las posibles subsecuencias de la array dada.
Complejidad de Tiempo: O(K * N K )
Espacio Auxiliar: O(K)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar todos los números pares e impares de la array dada en dos arrays separadas y ordenar ambas arrays . Finalmente, use la técnica Greedy para calcular la suma máxima incluso subsecuencia de tamaño K . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxSum para almacenar la suma par máxima de una subsecuencia de la array dada.
- Inicialice dos arrays, digamos Even[] y Odd[] para almacenar todos los números pares e impares de la array dada, respectivamente.
- Recorra la array dada y almacene todos los números pares e impares de la array dada en la array Even[] y Odd[] respectivamente.
- Ordenar arreglos pares [] e impares[] .
- Inicialice dos variables, digamos i y j para almacenar el índice de la array Even[] y Odd[] respectivamente.
- Atraviese las arrays Even[] , Odd[] y verifique las siguientes condiciones:
- Si K % 2 == 1 , entonces incremente el valor de maxSum por Even[i] .
- De lo contrario, incremente el valor de maxSum por max(Even[i] + Even[i – 1], Odd[j] + Odd[j – 1]) .
- Finalmente, imprima el valor de maxSum .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
18
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)