Cómo escribir un algoritmo para encontrar el número máximo que se puede obtener combinando dos números adyacentes, de modo que si a = b, entonces a + b, sino min (a, b)

Answer 1

Por ahora, el único enfoque factible que tengo.

Defina [math] f (i, j, k) [/ math] como verdadero / falso si los elementos [math] a_i, a_ {i + 1}, …, a_j [/ math] se pueden combinar de alguna manera para formar un valor final [matemática] k [/ matemática]. Necesitamos ver cuál podría ser el valor máximo, donde creo que [math] \ textrm {MAXVAL = max_a * n} [/ math] es un buen límite superior.

Ahora, podemos construir recurrencias de la siguiente manera:

Repetimos [math] l [/ math] suponiendo que finalmente combinamos dos valores generados por subarreglos [math] [i, l] [/ math] y [math] [l + 1, j] [/ math]. Ahora, aquí usamos el hecho de que si ambas submatrices generan un mismo valor final [math] \ frac {k} {2} [/ math] (suponiendo que [math] k [/ math] es divisible por 2), podemos generar [math] k [/ math], o de lo contrario, una de las submatrices debería generar el valor [math] k [/ math] y otra submatriz debería generar un valor de al menos [math] k [/ math].

Entonces, el pseudocódigo para las recurrencias se ve algo así (espero que pueda escribir casos base usted mismo):

f (i, j, k)

// punto de quiebre es l
para l = i a j-1
// mantener el valor máximo que ambos pueden generar
max1 = max2 = 0
para x = 1 a MAXVAL:
si f (i, l, x)
max1 = max (max1, x)

si f (l + 1, j, x)
max2 = max (max2, x)

// ambos pueden generar k / 2
si k% 2 == 0 yf (i, l, k / 2) yf (l + 1, j, k / 2)
volver 1

si f (i, l, k) y max2> k
volver 1

si f (l + 1, j, k) y max1> k
volver 1

volver 0

Ahora, podemos iterar sobre todos los valores posibles [matemática] k [/ matemática] para ver cuál [matemática] f (0, N-1, k) [/ matemática] da el máximo. Entonces, la complejidad es [matemática] O (n ^ 5 * \ textrm {max_a} ^ 2) [/ matemática].

cc Arjun Arul para sugerir algo mejor, como siempre. 🙂

Editar: vea su comentario sobre cómo puede reducir la complejidad por un factor de [math] \ textrm {max_a} [/ math].

Answer 2

Dada una matriz A que contiene los valores, así es como debería verse el pseudocódigo de recursión

m [i, j] =

SI i == j entonces un [i] ELSE {

x = suma de elementos entre a [i] a a [j]

max (x, m [i, k] + m [k + 1, j], para todas las k de manera que i

}

m [0, array_length – 1] le dará la respuesta final.

Answer 3

Esta respuesta ha demostrado ser incorrecta.

Haga esto recursivamente:

Si el número de ocurrencias del valor más bajo es impar, el valor más bajo es la salida. De lo contrario, descarte todo entre las dos primeras instancias del valor más bajo y luego sume el par.

Eso es.

{8 1 2 4 8 16 8 8 4 2 1} se convierte en {8 1 1} se convierte en {8 2} se convierte en 2

Editar: como señaló Lalit Kundu en los comentarios, este algoritmo no funciona.

Aunque inicialmente pensé que era un caso fronterizo, parece que su ejemplo muestra lo que está fundamentalmente mal con mi solución.
A menos que busquemos muchos casos especiales feos, creo que esta solución falla.