Encontrar la suma máxima según la regla

Tengo que encontrar la suma máxima de elementos en un arreglo de enteros, de acuerdo con la regla:

Si se agrega el segundo (o cualquier elemento consecutivo) a la suma, solo se agrega la mitad del valor. Para evitar esto, puedes omitir un elemento.

Por ejemplo, tenemos una entrada como esta [4, 2, 5, 1, 5]
El resultado debería ser 14. En este caso, tomamos los elementos en las posiciones 0, 2 y 4 (4 + 5 + 5 = 14) y omitimos los elementos en las posiciones 1 y 3.

Otro ejemplo sería una entrada como esta [3, 1, 10, 6, 3, 10]
En este caso, la respuesta debería ser 26. Tomamos los elementos en las posiciones 0, 2, 3, 5 y omitimos los elementos en las posiciones 1 y 4. Por lo tanto, la suma se cuenta como:

3 + 0 + 10 + 6/2 + 0 + 10 = 26

¿Alguien podría por favor explicarme el algoritmo para resolver este problema? ¿O al menos la dirección en la que debería intentar resolverlo? ¿Tiene esta tarea algo que ver con la programación dinámica? ¿O tal vez con la recursión?

Gracias anticipadas.

davy.ai

August 6, 2023 at 12:49 am

Para resolver este problema, un posible algoritmo es el siguiente:

Inicializar dos variables: “prev_skip” a 0 y “prev_take” al valor del primer elemento en el arreglo.
Recorrer el arreglo comenzando desde el segundo elemento:
a. Calcular el valor actual de “skip” como el máximo entre “prev_skip” y “prev_take”.
b. Calcular el valor actual de “take” como la suma del elemento actual y “prev_skip”.
c. Actualizar “prev_skip” y “prev_take” con los valores de “skip” y “take”, respectivamente.
Devolver el máximo entre “prev_skip” y “prev_take”.

Este algoritmo utiliza programación dinámica para llevar un seguimiento de la suma máxima que se puede obtener tanto al saltar como al tomar el elemento actual, basado en los resultados de los elementos anteriores. La naturaleza recurrente del problema se captura mediante la actualización de los valores de “skip” y “take” basados en los valores anteriores.

Aquí está la implementación en Python de este algoritmo:

def encontrar_suma_max(arr):
    prev_skip, prev_take = 0, arr[0]
    for i in range(1, len(arr)):
        skip = max(prev_skip, prev_take)
        take = arr[i] + prev_skip
        prev_skip, prev_take = skip, take
    return max(prev_skip, prev_take)

Ten en cuenta que la complejidad temporal de este algoritmo es O(n) y la complejidad espacial es O(1), ya que solo necesitamos llevar un seguimiento de los dos valores anteriores.

Answer

davy.ai

August 6, 2023 at 12:49 am
Para resolver este problema, un posible algoritmo es el siguiente:
1. Inicializar dos variables: “prev_skip” a 0 y “prev_take” al valor del primer elemento en el arreglo.
2. Recorrer el arreglo comenzando desde el segundo elemento:
  a. Calcular el valor actual de “skip” como el máximo entre “prev_skip” y “prev_take”.
  b. Calcular el valor actual de “take” como la suma del elemento actual y “prev_skip”.
  c. Actualizar “prev_skip” y “prev_take” con los valores de “skip” y “take”, respectivamente.
3. Devolver el máximo entre “prev_skip” y “prev_take”.
Este algoritmo utiliza programación dinámica para llevar un seguimiento de la suma máxima que se puede obtener tanto al saltar como al tomar el elemento actual, basado en los resultados de los elementos anteriores. La naturaleza recurrente del problema se captura mediante la actualización de los valores de “skip” y “take” basados en los valores anteriores.

Aquí está la implementación en Python de este algoritmo:
```
def encontrar_suma_max(arr):
    prev_skip, prev_take = 0, arr[0]
    for i in range(1, len(arr)):
        skip = max(prev_skip, prev_take)
        take = arr[i] + prev_skip
        prev_skip, prev_take = skip, take
    return max(prev_skip, prev_take)
```
Ten en cuenta que la complejidad temporal de este algoritmo es O(n) y la complejidad espacial es O(1), ya que solo necesitamos llevar un seguimiento de los dos valores anteriores.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Encontrar la suma máxima según la regla

Answer

davy.ai