Subsecuencia mínima de productos donde los elementos adyacentes están separados por una distancia máxima de K

Dada una array arr[] y un entero K , la tarea es encontrar el producto mínimo de una subsecuencia donde los elementos adyacentes de la subsecuencia están separados por una distancia máxima de K.
Nota: la subsecuencia debe incluir el primer y el último elemento de la array

Ejemplos: 

Entrada: arr[] = { 1, 2, 3, 4 }, K = 2 
Salida: 8 
El primer elemento en la subsecuencia es 1. Desde 1, podemos pasar a 2 o 3 (ya que K = 2). Podemos movernos a 3 y luego a 4 para tener un producto de 12. Sin embargo, también podemos movernos a 2 y luego a 4 para tener un producto de 8. Subsecuencia mínima del producto = { 1, 2, 4 }
Entrada: arr[ ] = { 2, 3 }, K = 2 
Salida: 6 

Enfoque ingenuo: un enfoque ingenuo es generar todas las subsecuencias de la array y mantener una diferencia de índices entre los elementos adyacentes y encontrar la subsecuencia mínima del producto. 
Enfoque eficiente: un enfoque eficiente es usar programación dinámica . Sea dp[i] el producto mínimo de elementos hasta el índice ‘i’ incluyendo arr[i] que están separados por una distancia máxima de K . Entonces dp[i] se puede formular de la siguiente manera: 

dp[i] = arr[i] * min{dp[j]} where j < i and 1 <= i - j <= K.

Para calcular dp[i] , una ventana de tamaño K se puede mantener y recorrer para encontrar el mínimo de dp[j] que luego se puede multiplicar por arr[i] . Sin embargo, esto dará como resultado una solución  O(N*K) .
Para optimizar aún más la solución, los valores del producto se pueden almacenar en un conjunto STL y luego se puede encontrar el valor mínimo del producto en tiempo O (log n) . Dado que almacenar productos puede ser una tarea engorrosa ya que el producto puede exceder fácilmente 10 ¹⁸ , almacenaremos los valores logarítmicos de los productos ya que logaritmo es una función monótona y la minimización de los valores logarítmicos implicará automáticamente la minimización de los productos.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the above approach.
#include <bits/stdc++.h>
 
#define mp make_pair
#define ll long long
using namespace std;
 
const int mod = 1000000007;
const int MAX = 100005;
 
// Function to get the minimum product of subsequence such that
// adjacent elements are separated by a max distance of K
int minimumProductSubsequence(int* arr, int n, int k)
{
    multiset<pair<double, int> > s;
 
    ll dp[MAX];
    double p[MAX];
 
    dp[0] = arr[0];
    p[0] = log(arr[0]);
 
    // multiset will hold pairs
    // pair = (log value of product, dp[j] value)
    // dp[j] = minimum product % mod
    // multiset will be sorted according to log values
    // Therefore, corresponding to the minimum log value
    // dp[j] value can be obtained.
    s.insert(mp(p[0], dp[0]));
 
    // For the first k-sized window.
    for (int i = 1; i < k; i++) {
 
        double l = (s.begin())->first;
        ll min = (s.begin())->second;
 
        // Update log value by adding previous
        // minimum log value
        p[i] = log(arr[i]) + l;
        // Update dp[i]
        dp[i] = (arr[i] * min) % mod;
 
        // Insert it again into the multiset
        // since it is within the k-size window
        s.insert(mp(p[i], dp[i]));
    }
 
    for (int i = k; i < n; i++) {
 
        double l = (s.begin())->first;
        ll min = (s.begin())->second;
 
        p[i] = log(arr[i]) + l;
        dp[i] = (arr[i] * min) % mod;
 
        // Eliminate previous value which falls out
        // of the k-sized window
        multiset<pair<double, int> >::iterator it;
        it = s.find(mp(p[i - k], dp[i - k]));
        s.erase(it);
 
        // Insert newest value to enter in
        // the k-sized window.
        s.insert(mp(p[i], dp[i]));
    }
 
    // dp[n - 1] will have minimum product %
    // mod such that adjacent elements are
    // separated by a max distance K
    return dp[n - 1];
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
 
    cout << minimumProductSubsequence(arr, n, k);
 
    return 0;
}

# Python3 implementation of the above approach.
import math
  
mod = 1000000007;
MAX = 100005;
  
# Function to get the minimum product of subsequence such that
# adjacent elements are separated by a max distance of K
def minimumProductSubsequence(arr, n, k):
 
    s = []
  
    dp = [0 for i in range(MAX)];
    p = [0.0 for i in range(MAX)];
  
    dp[0] = arr[0];
    p[0] = math.log(arr[0]);
  
    # multiset will hold pairs
    # pair = (log value of product, dp[j] value)
    # dp[j] = minimum product % mod
    # multiset will be sorted according to log values
    # Therefore, corresponding to the minimum log value
    # dp[j] value can be obtained.
    s.append([p[0], dp[0]]);
    s.sort()
     
    # For the first k-sized window.
    for i in range(1, k):
         
        l = s[0][0]
        min = s[0][1]
  
        # Update log value by adding previous
        # minimum log value
        p[i] = math.log(arr[i]) + l;
       
        # Update dp[i]
        dp[i] = (arr[i] * min) % mod;
  
        # Insert it again into the multiset
        # since it is within the k-size window
        s.append([p[i], dp[i]]);
        s.sort()
     
    for i in range(k, n):
  
        l = s[0][0]
        min = s[0][1]
 
        p[i] = math.log(arr[i]) + l;
        dp[i] = (arr[i] * min) % mod;
  
        # Eliminate previous value which falls out
        # of the k-sized window
        if [p[i - k], dp[i - k]] in s:
            s.pop(s.index([p[i - k], dp[i - k]]))
  
        # Insert newest value to enter in
        # the k-sized window.
        s.append([p[i], dp[i]]);
        s.sort()
     
    # dp[n - 1] will have minimum product %
    # mod such that adjacent elements are
    # separated by a max distance K
    return dp[n - 1];
 
# Driver Code
if __name__=='__main__':
     
    arr = [ 1, 2, 3, 4 ]
    n = len(arr)
     
    k = 2;
  
    print(minimumProductSubsequence(arr, n, k))
  
# This code is contributed by rutvik_56

8

Complejidad de Tiempo: O(N* log(N))
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.