Dada una cadena que contiene solo los caracteres '(' y ')', se debe encontrar la longitud de la subcadena más larga de paréntesis válidos (bien formados).

Para la cadena "(()", la subcadena válida más larga es "()", con longitud = 2.

Otro ejemplo es ")()())", donde la subcadena válida más larga es "()()", con longitud = 4.

Análisis:

Para resolver este problema, podemos utilizar programación dinámica en una dimensión, procesando la cadena en dirección inversa. Supongamos que la expresión de paréntesis de entrada es la cadena s, y mantenemos un array unidimensional dp[] de longitud s.length, inicializado con ceros. dp[i] representa la longitud de la subcadena de paréntesis válida más larga que comienza en s[i] y termina en algún punto hasta el final de la cadena.

La relación es la siguiente:

• dp[s.length - 1] = 0
• Procesamos i desde n-2 hacia 0 para calcluar dp[], registrando el valor máximo. Si s[i] == '(', entonces calculamos el valor de dp[i] en la cadena desde i hasta el final. Este cálculo se realiza en dos pasos, utilizando dp[i+1] (que ya fue calculado en la iteración anterior):

1. Encontramos la longitud de la subcadena válida que comienza en i+1, es decir, dp[i+1], y saltamos esta subcadena válida para ver el siguiente carácter en la posición j = i + 1 + dp[i+1]. Si j está dentro de los límites y s[j] == ')', entonces s[i...j] forma una subcadena válida, y dp[i] = dp[i+1] + 2.
2. Después de obtener la longitud de la subcadena válida s[i...j], si j+1 está dantro de los límites, entonces dp[i] también debe incluir la longitud de la subcadena válida que comienza en j+1, es decir, dp[j+1].

class Solucion {
public:
    int longitudParentesisValidoMasLarga(string s) {
        int tam = s.length();
        if(tam < 2)
          return 0;
        int maxima = 0;
        int *dp = new int[tam];
        for(int k = 0; k < tam; k++) // Inicializar el array con ceros
         dp[k] = 0;
        for(int i = tam-2; i >= 0; i--)
        {
          if(s[i] == '(') // Solo procesamos paréntesis izquierdos
          {
            int j = i+1+dp[i+1]; // Posición potencial del paréntesis derecho coincidente
            if(j < tam && s[j] == ')') // Verificar que esté dentro de los límites
            {
              dp[i] = dp[i+1] + 2; // Encontró paréntesis coincidente
              if(j+1 < tam) // Conectar subsecuencias válidas
                dp[i] += dp[j+1]; // Agregar longitud de subsecuencia válida siguiente
            }
            if(dp[i] > maxima)
              maxima = dp[i]; // Actualizar longitud máxima
          }
          
        }
        return maxima;
    }
};

Otro enfoque:

Utilizar una pila que no almacene caracteres, sino las posiciones de los paréntesis izquierdos, usando paréntesis derechos no coincidentes como separadores.

class Solucion {
public:
    int resultado;
    int suma;
    int longitudParentesisValidoMasLarga(string s) {
        resultado = suma = 0;
        deque<int> pila;
        if(s.size() <= 0)
            return 0;
        int ultimo = -1;
        for(int i = 0; i < s.size(); i ++) {
            if(s[i] == '(') {
                pila.push_back(i);
            }else{
                if(pila.empty()) {
                    ultimo = i;
                }else{
                    pila.pop_back();
                    if(pila.empty()) {
                        resultado = max(resultado, i-ultimo);
                    }else{
                        resultado = max(resultado, i-pila.back());
                    }
                     
                }
            }
        }
        return resultado;
    }
};