Dada una array arr[] que consta de N enteros y un entero K , la tarea es imprimir la suma máxima posible en una subsecuencia que satisfaga las siguientes condiciones:
- Los elementos arr[N – 1] y arr[0] se incluyen en la subsecuencia.
- Los elementos adyacentes en la subsecuencia pueden estar a una distancia de, como máximo , índices K.
Ejemplos:
Entrada: arr[] = {10, -5, -2, 4, 0, 3}, K = 3
Salida: 17
Explicación:
una de las formas posibles es la siguiente:
incluir arr[0] en la subsecuencia. Suma = 10.
Incluya arr[3] en la subsecuencia. Por lo tanto, sum = 10 + 4 = 14.
Incluya arr[5] en la subsecuencia. Por lo tanto, suma total = 14 + 3 = 17.
Por lo tanto, la suma máxima posible es 17.Entrada: arr[] = {1, -5, -20, 4, -1, 3, -6, -3}, K = 2
Salida: 0
Enfoque ingenuo: el enfoque más simple es encontrar todas las subsecuencias posibles de arr[] con una diferencia máxima de K entre los índices de los elementos adyacentes, comenzando desde el índice 0 y terminando en el índice (N – 1) . Calcular la suma de todas esas subsecuencias. Finalmente, imprima el máximo de todas las sumas obtenidas.
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de un algoritmo codicioso y deque . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos dp[] , para almacenar el valor máximo obtenido hasta el índice actual.
- Inicialice un deque de pares, digamos Q , para almacenar el par {dp[i], i} .
- Asigne el valor de arr[0] a dp[0] y empuje el par {dp[0], 0} en el deque .
- Recorra la array dada arr[] usando la variable i y realice los siguientes pasos:
- Incremente dp[i] por la suma de arr[i] y el valor máximo en el deque, es decir, dp[i] = arr[i] + Q[0][0] .
- Recorra el deque Q desde el final y extraiga el último elemento si Q[-1][0] es menor que dp[i] .
- Agregue el par {dp[i], i} en el deque.
- Compruebe si el índice del primer elemento del deque q es igual a (i – K) o no y luego extraiga el primer elemento del deque Q.
- Después de completar los pasos anteriores, imprima el valor almacenado en el último índice de dp[] , es decir, dp[N – 1] como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach #include<bits/stdc++.h> using namespace std; // Function to find maximum sum // of a subsequence satisfying // the given conditions int maxResult(int arr[], int k, int n){ // Stores the maximum sum int dp[n] = {0}; // Starting index of // the subsequence dp[0] = arr[0]; // Stores the pair of maximum value // and the index of that value deque<pair<int,int>> q; q.push_back({arr[0], 0}); // Traverse the array for (int i = 1; i < n; i++) { // Increment the first value // of deque by arr[i] and // store it in dp[i] dp[i] = arr[i] + q.front().first; // Delete all the values which // are less than dp[i] in deque while (q.size() > 0 and q.back().first < dp[i]) q.pop_back(); // Append the current pair of // value and index in deque q.push_back({dp[i], i}); // If first value of the // queue is at a distance > K if (i - k == q.front().second) q.pop_front(); } // Return the value at the last index return dp[n - 1]; } // Driver Code int main() { int arr[] = {10, -5, -2, 4, 0, 3}; int K = 3; int n = sizeof(arr)/sizeof(arr[0]); cout<<maxResult(arr, K,n); } // This code is contributed by ipg2016107.
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Pair class Store (x,y) Pair static class Pair { int x, y; Pair(int x, int y) { this.x = x; this.y = y; } } // Function to find maximum sum // of a subsequence satisfying // the given conditions private static int maxResult(int[] arr, int k, int n) { // Stores the maximum sum int dp[] = new int[n]; // Starting index of // the subsequence dp[0] = arr[0]; // Stores the pair of maximum value // and the index of that value Deque<Pair> q = new LinkedList<Pair>(); q.add(new Pair(arr[0], 0)); // Traverse the array for (int i = 1; i < n; i++) { // Increment the first value // of deque by arr[i] and // store it in dp[i] dp[i] = arr[i] + q.peekFirst().x; // Delete all the values which // are less than dp[i] in deque while (q.size() > 0 && q.peekLast().x < dp[i]) q.pollLast(); // Append the current pair of // value and index in deque q.add(new Pair(dp[i], i)); // If first value of the // queue is at a distance > K if (i - k == q.peekFirst().y) q.pollFirst(); } // Return the value at the last index return dp[n - 1]; } // Driver Code public static void main(String[] args) { int arr[] = {10, -5, -2, 4, 0, 3}; int K = 3; int n = arr.length; System.out.println(maxResult(arr, K,n)); } } // This code is contributed by Dheeraj Bhagchandani.
Python3
# Python program for the above approach from collections import deque # Function to find maximum sum # of a subsequence satisfying # the given conditions def maxResult(arr, k): # Stores the maximum sum dp = [0]*len(arr) # Starting index of # the subsequence dp[0] = arr[0] # Stores the pair of maximum value # and the index of that value q = deque([(arr[0], 0)]) # Traverse the array for i in range(1, len(arr)): # Increment the first value # of deque by arr[i] and # store it in dp[i] dp[i] = arr[i] + q[0][0] # Delete all the values which # are less than dp[i] in deque while q and q[-1][0] < dp[i]: q.pop() # Append the current pair of # value and index in deque q.append((dp[i], i)) # If first value of the # queue is at a distance > K if i - k == q[0][1]: q.popleft() # Return the value at the last index return dp[-1] # Driver Code arr = [10, -5, -2, 4, 0, 3] K = 3 print(maxResult(arr, K))
C#
// C# program to implement above approach using System; using System.Collections; using System.Collections.Generic; using System.Runtime.InteropServices; class GFG { class Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } // Function to find maximum sum // of a subsequence satisfying // the given conditions static int maxResult(int[] arr, int k, int n) { // Stores the maximum sum int[] dp = new int[n]; // Starting index of // the subsequence dp[0] = arr[0]; // Stores the pair of maximum value // and the index of that value List<Pair> q = new List<Pair>(); // Pointers to first and last element of Deque int l = 0, r= -1; q.Add(new Pair(arr[0], 0)); r++; // Traverse the array for (int i = 1 ; i < n ; i++) { // Increment the first value // of deque by arr[i] and // store it in dp[i] dp[i] = arr[i] + q[l].x; // Delete all the values which // are less than dp[i] in deque while (l<=r && q[r].x < dp[i]) r--; // Append the current pair of // value and index in deque if(r == q.Count - 1){ q.Add(new Pair(dp[i], i)); }else{ q[r+1] = new Pair(dp[i], i); } r++; // If first value of the // queue is at a distance > K if (i - k == q[l].y) l++; } // Return the value at the last index return dp[n - 1]; } // Driver Code public static void Main(string[] args){ int[] arr = new int[]{10, -5, -2, 4, 0, 3}; int K = 3; int n = arr.Length; Console.Write(maxResult(arr, K,n)); } } // This code is contributed by subhamgoyal2014.
17
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA