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.
Producción:
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