Haz un balance de corchetes con la puntuación más alta.
Pregunta:
Dada una matriz A de enteros y una puntuación S = 0. Para cada lugar en la matriz, puede hacer una de las siguientes acciones:
- Colocar un “(“. La puntuación sería S += Ai
- Colocar un “)”. La puntuación sería S -= Ai
- Salir
¿Cuál es la puntuación más alta que puede obtenerse de modo que los paréntesis estén equilibrados?
Límites:
- |Ai| <= 10^9
- Tamaño de la matriz A: <= 10^5
Nota:
He intentado muchas formas, pero mi mejor solución es una “fuerza bruta” que lleva O(3^n). ¿Hay alguna manera de resolver este problema en O(n.logn) o menos?
davy.ai
Para resolver este problema, podemos usar programación dinámica para realizar un seguimiento de la puntuación más alta que podemos obtener hasta cierto índice, manteniendo los paréntesis equilibrados.
Sea
dp[i][j]
la puntuación más alta que podemos obtener hasta el índicei
conj
paréntesis abiertos. El caso base esdp[0][0] = 0
.Para cada índice subsiguiente
i
en el arreglo, tenemos tres opciones:(
, entonces la puntuación aumentará enA[i]
y aumentaremosj
en 1. Por lo tanto, la puntuación seríadp[i][j] = dp[i-1][j-1] + A[i]
.Si colocamos un paréntesis cerrado,
)
, la puntuación se reducirá enA[i]
y mantendremosj
igual. Por lo tanto, la puntuación seríadp[i][j] = dp[i-1][j+1] - A[i]
.Si omitimos este índice, no pasa nada con la puntuación o
j
. Por lo tanto, la puntuación seríadp[i][j] = dp[i-1][j]
.Podemos elegir la puntuación más alta entre las tres opciones para actualizar
dp[i][j]
. La respuesta seríadp[n-1][0]
, donden
es el tamaño del arreglo.La complejidad temporal de este algoritmo es
O(n^2)
, que está dentro de los límites del problema.Aquí está el código Python para el algoritmo:
Nota: Este código se puede optimizar aún más al considerar solo los valores posibles de
j
para una secuencia equilibrada de paréntesis. El número máximo de paréntesis abiertos esn/2
, por lo que solo necesitamos considerar los valores dej
de0
an/2
.