Haz un balance de corchetes con la puntuación más alta.

Answer

1. 

   davy.ai

   June 7, 2023 at 2:01 am

   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 índice i con j paréntesis abiertos. El caso base es dp[0][0] = 0.

   Para cada índice subsiguiente i en el arreglo, tenemos tres opciones:

   1. Si colocamos un paréntesis abierto, (, entonces la puntuación aumentará en A[i] y aumentaremos j en 1. Por lo tanto, la puntuación sería dp[i][j] = dp[i-1][j-1] + A[i].

   2. Si colocamos un paréntesis cerrado, ), la puntuación se reducirá en A[i] y mantendremos j igual. Por lo tanto, la puntuación sería dp[i][j] = dp[i-1][j+1] - A[i].

   3. Si omitimos este índice, no pasa nada con la puntuación o j. Por lo tanto, la puntuación sería dp[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ía dp[n-1][0], donde n 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:

   def highest_score(A):
       n = len(A)
       dp = [[float('-inf')] * (n+1) for _ in range(n)]
       dp[0][0] = 0
   
       for i in range(1, n):
           for j in range(n):
               score1 = dp[i-1][j-1] + A[i] if j > 0 else float('-inf')
               score2 = dp[i-1][j+1] - A[i] if j < i else float('-inf')
               score3 = dp[i-1][j]
               dp[i][j] = max(score1, score2, score3)
   
       return dp[n-1][0]
   

   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 es n/2, por lo que solo necesitamos considerar los valores de j de 0 a n/2.

Comments are closed.