Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar la suma máxima de pares de elementos que están separados por al menos K índices.
Ejemplos:
Entrada: arr[] = {2, 4, 1, 6, 8}, K = 2
Salida: 12
Explicación:
Los elementos {1, 4} están separados por una distancia de K(= 2). La suma de pares {4, 8} es 4 + 8 = 12, que es el máximo.Entrada: arr[] = {1, 2, 3}, K = 1
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles de la array dada que están separados por K distancia e imprimir la suma máxima entre todos los pares posibles formados.
Complejidad Temporal: O(N 2 )
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.
Enfoque eficiente: el enfoque anterior se puede optimizar precalculando los máximos de prefijo para cada elemento de la array. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos res como INT_MIN , que almacena la suma máxima de pares válidos que están separados por K distancia en la array dada.
- Inicialice una array, digamos preMax[] , que almacene el elemento de array de valor máximo hasta cada índice i .
- Inicialice preMax[0] igual a arr[0] .
- Recorra la array sobre el rango [1, N – 1] y actualice el valor de preMax[i] al máximo de preMax[i – 1] y arr[i] .
- Ahora, itere sobre el rango [K, N – 1] , y para cada índice i , actualice el valor de res como el máximo de res y (arr[i] + preMax[i – K]) .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest sum
// pair that are K distant apart
int getMaxPairSum(int arr[], int N,
int K)
{
// Stores the prefix maximum array
int preMax[N];
// Base Case
preMax[0] = arr[0];
// Traverse the array and update
// the maximum value upto index i
for (int i = 1; i < N; i++) {
preMax[i] = max(preMax[i - 1],
arr[i]);
}
// Stores the maximum sum of pairs
int res = INT_MIN;
// Iterate over the range [K, N]
for (int i = K; i < N; i++) {
// Find the maximum value of
// the sum of valid pairs
res = max(res, arr[i]
+ preMax[i - K]);
}
// Return the resultant sum
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 8, 6, 3 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
cout << getMaxPairSum(arr, N, K);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to find the largest sum
// pair that are K distant apart
static int getMaxPairSum(int[] arr, int N, int K)
{
// Stores the prefix maximum array
int[] preMax = new int[N];
// Base Case
preMax[0] = arr[0];
// Traverse the array and update
// the maximum value upto index i
for (int i = 1; i < N; i++) {
preMax[i] = Math.max(preMax[i - 1], arr[i]);
}
// Stores the maximum sum of pairs
int res = Integer.MIN_VALUE;
// Iterate over the range [K, N]
for (int i = K; i < N; i++) {
// Find the maximum value of
// the sum of valid pairs
res = Math.max(res, arr[i] + preMax[i - K]);
}
// Return the resultant sum
return res;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 4, 8, 6, 3 };
int K = 3;
int N = arr.length;
System.out.print(getMaxPairSum(arr, N, K));
}
}
// This code is contributed by Kingash
Python3
# Python3` program for the above approach # Function to find the largest sum # pair that are K distant apart def getMaxPairSum(arr, N, K): # Stores the prefix maximum array preMax = [0]*N # Base Case preMax[0] = arr[0] # Traverse the array and update # the maximum value upto index i for i in range(1, N): preMax[i] = max(preMax[i - 1], arr[i]) # Stores the maximum sum of pairs res = -10**8 # Iterate over the range [K, N] for i in range(K, N): # Find the maximum value of # the sum of valid pairs res = max(res, arr[i] + preMax[i - K]) # Return the resultant sum return res # Driver Code if __name__ == '__main__': arr = [1, 2, 4, 8, 6, 3] K = 3 N = len(arr) print (getMaxPairSum(arr, N, K)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the largest sum
// pair that are K distant apart
static int getMaxPairSum(int[] arr, int N, int K)
{
// Stores the prefix maximum array
int[] preMax = new int[N];
// Base Case
preMax[0] = arr[0];
// Traverse the array and update
// the maximum value upto index i
for (int i = 1; i < N; i++) {
preMax[i] = Math.Max(preMax[i - 1], arr[i]);
}
// Stores the maximum sum of pairs
int res = Int32.MinValue;
// Iterate over the range [K, N]
for (int i = K; i < N; i++)
{
// Find the maximum value of
// the sum of valid pairs
res = Math.Max(res, arr[i] + preMax[i - K]);
}
// Return the resultant sum
return res;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 2, 4, 8, 6, 3 };
int K = 3;
int N = arr.Length;
Console.Write(getMaxPairSum(arr, N, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find the largest sum
// pair that are K distant apart
function getMaxPairSum(arr, N, K)
{
// Stores the prefix maximum array
var preMax = Array(N);
// Base Case
preMax[0] = arr[0];
// Traverse the array and update
// the maximum value upto index i
for (var i = 1; i < N; i++) {
preMax[i] = Math.max(preMax[i - 1],
arr[i]);
}
// Stores the maximum sum of pairs
var res = -1000000000;
// Iterate over the range [K, N]
for (var i = K; i < N; i++) {
// Find the maximum value of
// the sum of valid pairs
res = Math.max(res, arr[i]
+ preMax[i - K]);
}
// Return the resultant sum
return res;
}
// Driver Code
var arr = [1, 2, 4, 8, 6, 3];
var K = 3;
var N = arr.length;
document.write( getMaxPairSum(arr, N, K));
</script>
Producción:
9
Complejidad temporal: O(N)
Espacio auxiliar: O(N)