Subsecuencia de suma máxima compuesta como máximo de K elementos distantes, incluidos el primer y el último elemento de la array

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: 
 

  1. Los elementos arr[N – 1] y arr[0] se incluyen en la subsecuencia.
  2. 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:
  • 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *