Primero analicemos las soluciones subóptimas de la sección PUNTUACIÓN. Para el ~30\%~ de los puntos, la tarea podría haberse resuelto mediante una búsqueda exhaustiva. En otra palabras, podríamos haber modificado el arreglo de todas las formas posibles y, al final, generar el número mínimo de movimientos que conducen a la solución. Como podemos hacer ~(N - 1)~ diferentes uniones en un arreglo de longitud ~N~, y porque después de cada movimiento la longitud de la matriz disminuye en 1, llegamos a la conclusión de que la complejidad de esta solución es ~O (n!)~.

Primero observemos el primer y último miembro del arreglo. Ya que deseamos transformar el arreglo a un palíndromo, el primer miembro y el último deben ser iguales al final. Si no lo son iguales en el momento dado, obviamente al menos uno de ellos debe estar unido a su vecino. Este tipo de pensamiento nos lleva a una formulación recursiva de la solución. Sea ~f (l, r)~ el número mínimo de movimientos necesarios para que los elementos ~A [l], A [l + 1], ..., A [r - 1], A [r]~ se transformen en palíndromo. Dadas las observaciones anteriores,

• Si ~l > r, f (l, r) = 0~
• Si \(l <= r, f (l, r) = mínimo (1 + f (l + 1, r), 1 + f (l, r - 1), f (l + 1, r-1))\)

donde las dos primeras partes del segundo caso es válido si y solo si tiene ~A [l] = A [r]~. Observe que en cada paso del algoritmo, el valor ~A [l]~ es igual a la suma de todos sus predecesores, y ~A [r]~ es igual a la suma de todos sus sucesores, mientras que los elementos en el medio no se modifican. Usando un enfoque de programación dinámica, más precisamente la técnica de movilización, la complejidad de tal solución es ~O (n ^ 2)~, que es suficiente para el ~60\%~ de puntos.

Para obtener todos los puntos, necesitamos usar el hecho de que los números en la entrada son positivo. Como en el párrafo anterior, abordamos la tarea desde fuera hacia dentro. Cuándo nos centramos en un intervalo ~[l, r]~, diferenciamos entre un par de casos: Si tiene ~A [l] = A [r]~, entonces no necesitamos unir los elementos externos, sino que continuamos resolviendo el intervalo ~[l + 1, r-1]~. Si tiene ~A [l] < A [r]~, entonces seguramente no podemos beneficiarnos de unir los elementos ~A [r]~ y ~A [r - 1]~ porque su suma es necesariamente mayor que ~A [l]~ que no se puede dejar sin unir. Por lo tanto, lo haremos uniendo los elementos ~A [l]~ y ~A [l + 1]~ y continuamos resolviendo el intervalo ~[l + 1, r]~. Resolvemos análogamente el caso donde ~A [l] > A [r]~. Dado que disminuiremos el intervalo en al menos ~1~ en cada paso del algoritmo, podemos Concluimos que la complejidad del algoritmo es ~O (n)~, suficiente para todos los puntos.