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
Para resolver este problema, un posible algoritmo es el siguiente:
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.
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:
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.