Dada una array arr[] y un entero K , la tarea es encontrar y maximizar la suma de como máximo K elementos en la array tomando solo los elementos de las esquinas.
Un elemento de esquina es un elemento desde el principio de la array o desde el final de la array.
Ejemplos:
Entrada: N = 8, arr[] = {6, -1, 14, -15, 2, 1, 2, -5}, K = 4
Salida: 19
Explicación:
Aquí la elección óptima es elegir tres cartas del comienzo. Después de eso, si queremos elegir la siguiente carta, nuestros puntos disminuirán. Así que el máximo de puntos es arr[0] + arr[1] + arr[2] = 19.Entrada: N = 5, arr[] = {-2, -1, -6, -3, 1}, K = 2
Salida: 1
Aquí la elección óptima es elegir la última carta. Entonces, el máximo de puntos posibles es arr[4] = 1. Cualquier otra selección reducirá el valor.
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, utilizaremos Recursion . Como solo podemos tomar un valor de índice inicial o final, inicialice dos variables y tome como máximo K pasos y devuelva la suma máxima entre todas las combinaciones posibles. Actualice la suma máxima solo si es mayor que la suma anterior; de lo contrario, salte a la siguiente combinación posible. El enfoque recursivo tiene una complejidad exponencial debido a su subproblema superpuesto y su propiedad de subestructura óptima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Maximize sum of atmost
// K elements in Array by taking only corner elements
#include <bits/stdc++.h>
using namespace std;
// Function to return maximum points
int maxPointCount(int arr[], int K, int start, int end,
int points, int max_points)
{
if (K == 0) {
return max_points;
}
// Pick the start index
int points_start = points + arr[start];
// Update maximum points if necessary
max_points = max(max_points, points_start);
// Pick the end index
int points_end = points + arr[end];
// Update maximum points if necessary
max_points = max(max_points, points_end);
// Recursive call to get max value
return max(maxPointCount(arr, K - 1, start + 1, end,
points_start, max_points),
maxPointCount(arr, K - 1, start, end - 1,
points_end, max_points));
}
// Driver code
int main()
{
int arr[] = { -2, -1, -6, -3, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
int points = 0;
int max_points = 0;
// beginning index
int start = 0;
// end index
int end = N - 1;
cout << maxPointCount(arr, K, start,
end, points, max_points);
return 0;
}
Java
// Java implementation to Maximize
// sum of atmost K elements in Array
// by taking only corner elements
import java.util.*;
class GFG{
// Function to return maximum points
static int maxPointCount(int arr[], int K,
int start, int end,
int points, int max_points)
{
if (K == 0)
{
return max_points;
}
// Pick the start index
int points_start = points + arr[start];
// Update maximum points if necessary
max_points = Math.max(max_points, points_start);
// Pick the end index
int points_end = points + arr[end];
// Update maximum points if necessary
max_points = Math.max(max_points, points_end);
// Recursive call to get max value
return Math.max(maxPointCount(arr, K - 1,
start + 1, end,
points_start, max_points),
maxPointCount(arr, K - 1,
start, end - 1,
points_end, max_points));
}
// Driver code
public static void main(String[] args)
{
int arr[] = { -2, -1, -6, -3, 1 };
int N = arr.length;
int K = 2;
int points = 0;
int max_points = 0;
// Beginning index
int start = 0;
// End index
int end = N - 1;
System.out.print(maxPointCount(arr, K, start,
end, points,
max_points));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation to maximize sum # of atmost K elements in array by taking # only corner elements # Function to return maximum points def maxPointCount(arr, K, start, end, points, max_points): if (K == 0): return max_points # Pick the start index points_start = points + arr[start] # Update maximum points if necessary max_points = max(max_points, points_start) # Pick the end index points_end = points + arr[end] # Update maximum points if necessary max_points = max(max_points, points_end) # Recursive call to get max value return max(maxPointCount(arr, K - 1, start + 1, end, points_start, max_points), maxPointCount(arr, K - 1, start, end - 1, points_end, max_points)) # Driver code if __name__ == "__main__": arr = [ -2, -1, -6, -3, 1 ] N = len(arr) K = 2 points = 0 max_points = 0 # Beginning index start = 0 # end index end = N - 1 print(maxPointCount(arr, K, start, end, points, max_points)) # This code is contributed by chitranayal
C#
// C# implementation to Maximize
// sum of atmost K elements in Array
// by taking only corner elements
using System;
class GFG{
// Function to return maximum points
static int maxPointCount(int []arr, int K,
int start, int end,
int points, int max_points)
{
if (K == 0)
{
return max_points;
}
// Pick the start index
int points_start = points + arr[start];
// Update maximum points if necessary
max_points = Math.Max(max_points, points_start);
// Pick the end index
int points_end = points + arr[end];
// Update maximum points if necessary
max_points = Math.Max(max_points, points_end);
// Recursive call to get max value
return Math.Max(maxPointCount(arr, K - 1,
start + 1, end,
points_start, max_points),
maxPointCount(arr, K - 1,
start, end - 1,
points_end, max_points));
}
// Driver code
public static void Main(String[] args)
{
int []arr = { -2, -1, -6, -3, 1 };
int N = arr.Length;
int K = 2;
int points = 0;
int max_points = 0;
// Beginning index
int start = 0;
// End index
int end = N - 1;
Console.Write(maxPointCount(arr, K, start,
end, points,
max_points));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript implementation to Maximize
// sum of atmost K elements in Array
// by taking only corner elements
// Function to return maximum points
function maxPointCount(arr,K,start,end,points,max_points)
{
if (K == 0)
{
return max_points;
}
// Pick the start index
let points_start = points + arr[start];
// Update maximum points if necessary
max_points = Math.max(max_points, points_start);
// Pick the end index
let points_end = points + arr[end];
// Update maximum points if necessary
max_points = Math.max(max_points, points_end);
// Recursive call to get max value
return Math.max(maxPointCount(arr, K - 1,
start + 1, end,
points_start, max_points),
maxPointCount(arr, K - 1,
start, end - 1,
points_end, max_points));
}
// Driver code
let arr=[-2, -1, -6, -3, 1];
let N = arr.length;
let K = 2;
let points = 0;
let max_points = 0;
// Beginning index
let start = 0;
// End index
let end = N - 1;
document.write(maxPointCount(arr, K, start,
end, points,
max_points));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1
Enfoque eficiente:
para optimizar la solución anterior, implementaremos el concepto de ventana deslizante .
- Inicialmente, el tamaño de la ventana es 0 ya que no elegimos ningún elemento de la array. Tomamos dos variables curr_points y max_points para representar los puntos actuales y los puntos máximos.
- Considere los elementos K uno por uno desde el principio. Entonces, en cada paso, calculamos los puntos actuales y actualizamos los puntos máximos si es necesario y, después de incluir K elementos de la array, el tamaño de nuestra ventana deslizante se convierte en K, que es el máximo posible.
- Después de eso, en cada paso, seleccionamos elementos del final y eliminamos el elemento más a la derecha de la ventana previamente seleccionada con los primeros K elementos. Actualice curr_points y max_points. Al final, la ventana contiene K tarjetas del final de la array.
- Finalmente, en cada paso, retire la tarjeta más a la izquierda de la ventana previamente seleccionada con K elementos del final. Actualice los valores de curr_points y max_points. Al final, el tamaño de la ventana volverá a ser 0.
Veamos este ejemplo para entenderlo mejor, arr[] = {-2, -1, -6, -3, 1}, K = 2
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Maximize sum
// of atmost K elements in Array by taking
// only corner elements
#include <bits/stdc++.h>
using namespace std;
// Function to return maximum points
int maxPointCount(int arr[], int K, int size)
{
// Initialization of current points
// and max points so far
int curr_points = 0;
int max_points = 0;
// Add elements from the beginning
for (int i = 0; i < K; i++) {
curr_points += arr[i];
max_points = max(curr_points, max_points);
}
// Points to the end of array element
int j = size - 1;
// Add K elements from end of array
for (int i = K - 1; i >= 0; i--) {
curr_points = curr_points + arr[j] - arr[i];
max_points = max(curr_points, max_points);
// Decrement the value for j
j--;
}
j = size - K;
for (; j < size; j++) {
curr_points = curr_points - arr[j];
max_points = max(curr_points, max_points);
}
// Return the final result
return max_points;
}
// Driver code
int main()
{
int arr[] = { -2, -1, -6, -3, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << maxPointCount(arr, K, N);
return 0;
}
Java
// Java implementation to maximize
// sum of atmost K elements in Array
// by taking only corner elements
import java.util.Scanner;
import java.util.Arrays;
class GFG{
// Function to return maximum points
public static int maxPointCount(int arr[],
int K,
int size)
{
// Initialization of current points
// and max points so far
int curr_points = 0;
int max_points = 0;
// Add elements from the beginning
for(int i = 0; i < K; i++)
{
curr_points += arr[i];
max_points = Math.max(curr_points,
max_points);
}
// Points to the end of array element
int j = size - 1;
// Add K elements from end of array
for(int i = K - 1; i >= 0; i--)
{
curr_points = curr_points +
arr[j] - arr[i];
max_points = Math.max(curr_points,
max_points);
// Decrement the value for j
j--;
}
j = size - K;
for(; j < size; j++)
{
curr_points = curr_points - arr[j];
max_points = Math.max(curr_points,
max_points);
}
// Return the final result
return max_points;
}
// Driver code
public static void main(String args[])
{
int []arr = { -2, -1, -6, -3, 1 };
int N = arr.length;
int K = 2;
System.out.print(maxPointCount(arr, K, N));
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 implementation to # Maximize sum of atmost K # elements in Array by taking # only corner elements # Function to return maximum # points def maxPointCount(arr, K, size): # Initialization of current # points and max points so far curr_points = 0; max_points = 0; # Add elements from # the beginning for i in range(K): curr_points += arr[i]; max_points = max(curr_points, max_points) # Points to the end # of array element j = size - 1; # Add K elements from # end of array for i in range(K - 1, -1, -1): curr_points = (curr_points + arr[j] - arr[i]); max_points = max(curr_points, max_points); # Decrement the # value for j j -= 1; for j in range(size - K, size): curr_points = (curr_points - arr[j]); max_points = max(curr_points, max_points); # Return the final result return max_points; # Driver code if __name__ == "__main__": arr = [-2, -1, -6, -3, 1] N = len(arr) K = 2; print(maxPointCount(arr,K,N)) # This code is contributed by rutvik_56
C#
// C# implementation to maximize
// sum of atmost K elements in Array
// by taking only corner elements
using System;
class GFG{
// Function to return maximum points
static int maxPointCount(int[] arr, int K,
int size)
{
// Initialization of current points
// and max points so far
int curr_points = 0;
int max_points = 0;
// Add elements from the beginning
for(int i = 0; i < K; i++)
{
curr_points += arr[i];
max_points = Math.Max(curr_points,
max_points);
}
// Points to the end of array element
int j = size - 1;
// Add K elements from end of array
for(int i = K - 1; i >= 0; i--)
{
curr_points = curr_points + arr[j] -
arr[i];
max_points = Math.Max(curr_points,
max_points);
// Decrement the value for j
j--;
}
j = size - K;
for(; j < size; j++)
{
curr_points = curr_points - arr[j];
max_points = Math.Max(curr_points,
max_points);
}
// Return the final result
return max_points;
}
// Driver code
static void Main()
{
int[] arr = { -2, -1, -6, -3, 1 };
int N = arr.Length;
int K = 2;
Console.WriteLine(maxPointCount(arr, K, N));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript implementation to maximize
// sum of atmost K elements in Array
// by taking only corner elements
// Function to return maximum points
function maxPointCount(arr,K,size)
{
// Initialization of current points
// and max points so far
let curr_points = 0;
let max_points = 0;
// Add elements from the beginning
for(let i = 0; i < K; i++)
{
curr_points += arr[i];
max_points = Math.max(curr_points,
max_points);
}
// Points to the end of array element
let j = size - 1;
// Add K elements from end of array
for(let i = K - 1; i >= 0; i--)
{
curr_points = curr_points +
arr[j] - arr[i];
max_points = Math.max(curr_points,
max_points);
// Decrement the value for j
j--;
}
j = size - K;
for(; j < size; j++)
{
curr_points = curr_points - arr[j];
max_points = Math.max(curr_points,
max_points);
}
// Return the final result
return max_points;
}
// Driver code
let arr=[ -2, -1, -6, -3, 1 ];
let N = arr.length;
let K = 2;
document.write(maxPointCount(arr, K, N));
// This code is contributed by rag2127
</script>
Producción:
1
Complejidad de tiempo: O (n)
Espacio auxiliar: O (1)
Artículo similar : Maximice la suma de K elementos en Array tomando solo elementos de esquina
Publicación traducida automáticamente
Artículo escrito por animesh_ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA