题解 | 最长的括号子串

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型
 */
 #define max(x,y)   (x>y?x:y)
#include <string.h>
int longestValidParentheses(char* s ) {
    // write code here
    /*dp数组的定义方式：
    1.dp[i]表示从0到i-1这个长度的括号子串的长度
    2.dp[i]表示以i-1为结尾的括号字串的长度
    */
    /*我打算采用第1种定义方式*/
   /*再次思考还是认为应该采用第二种定义方法*/
    int n = strlen(s);
    char stack[n];
    int index = 0;;
    int dp[n+1];
    int res = 0; /*记录最大的长度*/
    memset(dp,0,sizeof(dp)); //初始化，都默认是0
    for(int i = 1;i<=n;i++)
    {
        if(s[i-1] == '(')
        {
            //入栈
            stack[index++] = '(';
        }
        else {
            if(index >0)
            {
                if(stack[index-1] =='(')
                {
                    --index; //出栈
                     dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2];//核心就是这个状态转移方程的确定
                }
                //寻找最大值
                res = max(res,dp[i]);
            }
        }
    }
    return res;
}