Maximizar el producto de la suma de dígitos de pares consecutivos en una subsecuencia de longitud K

Dada una array de enteros arr[] , la tarea es maximizar el producto de la suma de dígitos de cada par consecutivo en una subsecuencia de longitud K .
Nota: K siempre es par porque los pares se formarán con una longitud uniforme.

Ejemplos:  

Entrada: arr[] = {2, 100, 99, 3, 16}, K = 4 
Salida: 128 
La subsecuencia óptima de longitud 4 es [2, 100, 99, 16] 
La suma de dígitos = 2, 2, 18 y 7 respectivamente. 
Entonces el producto de sumas de dígitos en pares = 2 * 1 + 18 * 7 = 2 + 126 = 128 , que es el máximo.

Entrada: arr[] = {10, 5, 9, 101, 24, 2, 20, 14}, K = 6 
Salida: 69 
La subsecuencia óptima de longitud 6 = [10, 5, 9, 24, 2, 14] 
La suma de dígitos = 1, 5, 9, 6, 2 y 5 respectivamente. 
Entonces el producto de sumas de dígitos en pares = 1 * 5 + 9 * 6 + 2 * 5 = 5 + 54 + 10 = 69 , que es el máximo. 

Enfoque: La idea es utilizar Programación Dinámica . Como necesitamos encontrar pares en la array incluyendo o excluyendo algunos de los elementos de la array para formar una subsecuencia. Dejemos que DP[i][j][k] sea nuestra array dp que almacena el producto máximo de la suma de los dígitos de los elementos hasta el índice i que tiene una longitud j y el último elemento K .

Observaciones:  

• Longitud impar: al elegir la subsecuencia de longitud par, cuando la longitud actual de la subsecuencia elegida es impar, entonces se debe elegir el par para el último elemento. Por lo tanto, tenemos que calcular el producto de la suma de los elementos último y actual y recurrimos manteniendo el último como 0 en la siguiente llamada para una longitud uniforme .
  
• Longitud par: al elegir la subsecuencia de longitud impar, cuando la longitud actual de la subsecuencia elegida es par, solo tenemos que seleccionar el primer elemento del par. Por lo tanto, simplemente seleccionamos el elemento actual como el último elemento para la próxima llamada recursiva y buscamos el segundo elemento para este par en la próxima llamada recursiva.
  
• Excluir elemento: otra opción para el elemento actual es excluir el elemento actual y elegir más elementos.
  

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

// C++ implementation to find the
// maximum product of the digit
// sum of the consecutive pairs of
// the subsequence of the length K
 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
int dp[1000][MAX][MAX];
 
// Function to find the product
// of two numbers digit sum
// in the pair
int productDigitSum(int x, int y)
{
    int sumx = 0;
 
    // Loop to find the digits of
    // the number
    while (x) {
        sumx += (x % 10);
        x /= 10;
    }
    int sumy = 0;
 
    // Loop to find the digits
    // of other number
    while (y) {
        sumy += (y % 10);
        y /= 10;
    }
    return (sumx * sumy);
}
 
// Function to find the subsequence
// of the length K
int solve(int arr[], int i, int len,
          int prev, int n, int k)
{
    // Base Case
    if (len == k)
        return 0;
 
    // Condition when we didn't reach
    // the length K, but ran out of
    // elements of the array
    if (i == n)
        return INT_MIN;
 
    // Condition if already calculated
    if (dp[i][len][prev])
        return dp[i][len][prev];
 
    int inc = 0, exc = 0;
 
    // If length upto this point is odd
    if (len & 1) {
 
        // If length is odd, it means we need
        // second element of this current pair,
        // calculate the product of digit sum of
        // current and previous element and recur
        // by moving towards next index
        inc = productDigitSum(arr[prev],
                              arr[i])
              + solve(arr, i + 1,
                      len + 1, 0, n, k);
    }
 
    // If length upto this point is even
    else {
        inc = solve(arr, i + 1, len + 1, i, n, k);
    }
 
    // Exclude this current element
    // and recur for next elements.
    exc = solve(arr, i + 1, len, prev, n, k);
 
    // return by memoizing it, by selecting
    // the maximum among two choices.
    return dp[i][len][prev] = max(inc, exc);
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 5, 9, 101, 24, 2, 20, 14 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 6;
    cout << solve(arr, 0, 0, 0, n, k);
}

// Java implementation to find the
// maximum product of the digit
// sum of the consecutive pairs of
// the subsequence of the length K
import java.util.*;
 
class GFG{
     
static int MAX = 100;
static int dp[][][] = new int[1000][MAX][MAX];
 
// Function to find the product
// of two numbers digit sum
// in the pair
static int productDigitSum(int x, int y)
{
    int sumx = 0;
 
    // Loop to find the digits
    // of the number
    while (x > 0)
    {
        sumx += (x % 10);
        x /= 10;
    }
    int sumy = 0;
 
    // Loop to find the digits
    // of other number
    while (y > 0)
    {
        sumy += (y % 10);
        y /= 10;
    }
    return (sumx * sumy);
}
 
// Function to find the subsequence
// of the length K
static int solve(int arr[], int i, int len,
                  int prev, int n, int k)
{
     
    // Base Case
    if (len == k)
        return 0;
 
    // Condition when we didn't reach
    // the length K, but ran out of
    // elements of the array
    if (i == n)
        return Integer.MIN_VALUE;
 
    // Condition if already calculated
    if (dp[i][len][prev] != 0)
        return dp[i][len][prev];
 
    int inc = 0, exc = 0;
 
    // If length upto this point is odd
    if ((len & 1) != 0)
    {
 
        // If length is odd, it means we need
        // second element of this current pair,
        // calculate the product of digit sum of
        // current and previous element and recur
        // by moving towards next index
        inc = (productDigitSum(arr[prev], arr[i]) +
               solve(arr, i + 1, len + 1, 0, n, k));
    }
 
    // If length upto this point is even
    else
    {
        inc = solve(arr, i + 1, len + 1, i, n, k);
    }
 
    // Exclude this current element
    // and recur for next elements.
    exc = solve(arr, i + 1, len, prev, n, k);
 
    // Return by memoizing it, by selecting
    // the maximum among two choices.
    return dp[i][len][prev] = Math.max(inc, exc);
}
 
// Driver Code
public static void main(String []args)
{
    int arr[] = { 10, 5, 9, 101, 24, 2, 20, 14 };
    int n = arr.length;
    int k = 6;
     
    System.out.print(solve(arr, 0, 0, 0, n, k));
}
}
 
// This code is contributed by chitranayal

# Python3 implementation to find the
# maximum product of the digit
# sum of the consecutive pairs of
# the subsequence of the length K
import sys
 
MAX = 100
dp = []
 
for i in range(1000):
    temp1 = []
    for j in range(MAX):
        temp2 = []
         
        for k in range(MAX):
            temp2.append(0)
        temp1.append(temp2)
         
    dp.append(temp1)
 
# Function to find the product
# of two numbers digit sum
# in the pair
def productDigitSum(x, y):
    sumx = 0
     
    # Loop to find the digits of
    # the number
    while x:
        sumx += x % 10
        x = x // 10
         
    sumy = 0
     
    # Loop to find the digits
    # of other number
    while y:
        sumy += y % 10
        y = y // 10
     
    return sumx * sumy
 
# Function to find the subsequence
# of the length K
def solve(arr, i, len, prev, n, k):
     
    # Base case
    if len == k:
        return 0
     
    # Condition when we didn't reach
    # the length K, but ran out of
    # elements of the array
    if i == n:
        return -sys.maxsize - 1
     
    # Condition if already calculated
    if dp[i][len][prev]:
        return dp[i][len][prev]
     
    # If length upto this point is odd
    if len & 1:
         
        # If length is odd, it means we need
        # second element of this current pair,
        # calculate the product of digit sum of
        # current and previous element and recur
        # by moving towards next index
        inc = (productDigitSum(arr[prev], arr[i]) +
               solve(arr, i + 1, len + 1, i, n, k))
    else:
         
        # If length upto this point is even
        inc = solve(arr, i + 1, len + 1, i, n, k)
     
    # Exclude this current element
    # and recur for next elements.
    exc = solve(arr, i + 1, len, prev, n, k)
     
    # Return by memoizing it, by selecting
    # the maximum among two choices.
    dp[i][len][prev] = max(inc, exc)
    return dp[i][len][prev]
 
# Driver code
arr = [ 10, 5, 9, 101, 24, 2, 20, 14 ]
n = len(arr)
k = 6
print(solve(arr, 0, 0, 0, n, k))
 
# This code is contributed by Shivam Singh

// C# implementation to find the
// maximum product of the digit
// sum of the consecutive pairs of
// the subsequence of the length K
using System;
class GFG{
     
static int MAX = 100;
static int [, ,]dp = new int[1000, MAX, MAX];
 
// Function to find the product
// of two numbers digit sum
// in the pair
static int productDigitSum(int x, int y)
{
    int sumx = 0;
 
    // Loop to find the digits
    // of the number
    while (x > 0)
    {
        sumx += (x % 10);
        x /= 10;
    }
    int sumy = 0;
 
    // Loop to find the digits
    // of other number
    while (y > 0)
    {
        sumy += (y % 10);
        y /= 10;
    }
    return (sumx * sumy);
}
 
// Function to find the subsequence
// of the length K
static int solve(int []arr, int i, int len,
                 int prev, int n, int k)
{
     
    // Base Case
    if (len == k)
        return 0;
 
    // Condition when we didn't reach
    // the length K, but ran out of
    // elements of the array
    if (i == n)
        return Int32.MinValue;
 
    // Condition if already calculated
    if (dp[i, len, prev] != 0)
        return dp[i, len, prev];
 
    int inc = 0, exc = 0;
 
    // If length upto this point is odd
    if ((len & 1) != 0)
    {
 
        // If length is odd, it means we need
        // second element of this current pair,
        // calculate the product of digit sum of
        // current and previous element and recur
        // by moving towards next index
        inc = (productDigitSum(arr[prev], arr[i]) +
               solve(arr, i + 1, len + 1, 0, n, k));
    }
 
    // If length upto this point is even
    else
    {
        inc = solve(arr, i + 1, len + 1, i, n, k);
    }
 
    // Exclude this current element
    // and recur for next elements.
    exc = solve(arr, i + 1, len, prev, n, k);
 
    // Return by memoizing it, by selecting
    // the maximum among two choices.
    return dp[i, len, prev] = Math.Max(inc, exc);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 10, 5, 9, 101, 24, 2, 20, 14 };
    int n = arr.Length;
    int k = 6;
     
    Console.Write(solve(arr, 0, 0, 0, n, k));
}
}
 
// This code is contributed by Nidhi_biet

<script>
// Javascript implementation to find the
// maximum product of the digit
// sum of the consecutive pairs of
// the subsequence of the length K
 
 
const MAX = 100;
let dp = []
 
 
for (let i = 0; i < 1000; i++) {
    let temp1 = [];
    for (let j = 0; j < MAX; j++) {
        let temp2 = [];
        for (let k = 0; k < MAX; k++) {
            temp2.push(0)
        }
        temp1.push(temp2)
    }
    dp.push(temp1)
}
 
// Function to find the product
// of two numbers digit sum
// in the pair
function productDigitSum(x, y) {
    let sumx = 0;
 
    // Loop to find the digits of
    // the number
    while (x) {
        sumx += (x % 10);
        x = Math.floor(x / 10);
    }
    let sumy = 0;
 
    // Loop to find the digits
    // of other number
    while (y) {
        sumy += (y % 10);
        y = Math.floor(y / 10);
    }
    return (sumx * sumy);
}
 
// Function to find the subsequence
// of the length K
function solve(arr, i, len, prev, n, k) {
    // Base Case
    if (len == k)
        return 0;
 
    // Condition when we didn't reach
    // the length K, but ran out of
    // elements of the array
    if (i == n)
        return Number.MIN_SAFE_INTEGER;
 
    // Condition if already calculated
    if (dp[i][len][prev])
        return dp[i][len][prev];
 
    let inc = 0, exc = 0;
 
    // If length upto this point is odd
    if (len & 1) {
 
        // If length is odd, it means we need
        // second element of this current pair,
        // calculate the product of digit sum of
        // current and previous element and recur
        // by moving towards next index
        inc = productDigitSum(arr[prev],
            arr[i])
            + solve(arr, i + 1,
                len + 1, 0, n, k);
    }
 
    // If length upto this point is even
    else {
        inc = solve(arr, i + 1, len + 1, i, n, k);
    }
 
    // Exclude this current element
    // and recur for next elements.
    exc = solve(arr, i + 1, len, prev, n, k);
 
    // return by memoizing it, by selecting
    // the maximum among two choices.
    return dp[i][len][prev] = Math.max(inc, exc);
}
 
// Driver Code
 
let arr = [10, 5, 9, 101, 24, 2, 20, 14];
let n = arr.length;
let k = 6;
document.write(solve(arr, 0, 0, 0, n, k));
 
 
// This code is contributed by _saurabh_jaiswal
</script>

69