思路1：這個(gè)序列問題，很容易聯(lián)想到用動(dòng)態(tài)規(guī)劃的思路來解最長公共字符串的問題，區(qū)別在于，在求最長公共字符串的時(shí)候，子狀態(tài)從兩個(gè)相鄰字符開始判斷，如果這兩個(gè)字符不相等，則包含這兩個(gè)相鄰字符的一定不是公共字符串。而對于本題，如果兩個(gè)相鄰的括號不匹配，比如兩個(gè)都是'('、'('，這兩個(gè)不匹配，但以這兩個(gè)子串為基礎(chǔ)的其他子串不一定無法組成有效的括號，比如連續(xù)四個(gè)括號分別為'( ( ) )'這樣的形式，無法從之前計(jì)算的兩個(gè)右括號不匹配的情況推出現(xiàn)在四個(gè)括號的匹配情況。那么問題來了，針對本題的最優(yōu)子狀態(tài)應(yīng)該怎么去找呢？
通過分析：兩個(gè)匹配的左右括號，一定是相鄰最近的匹配對，也就是最里層的括號一定是優(yōu)先匹配，然后在逐層向外匹配，比如上述的四個(gè)連續(xù)括號'( ( ) )'的情況，一定是中間兩個(gè)先匹配，然后再匹配外層的兩個(gè)。如果我們在匹配第一個(gè)'('的時(shí)候，已經(jīng)提前知道第二個(gè)和第三個(gè)已經(jīng)組合為一個(gè)有效括號的話，那第一個(gè)就可以直接去匹配第四個(gè)左括號了，這樣的話，對于第一個(gè)右括號，最長匹配有效括號長度就是4。
也就是說，如果從左邊第一個(gè)匹配的時(shí)候，提前知道他右側(cè)的已經(jīng)匹配匹配好的最大長度了，那么就可以跳過已經(jīng)匹配完成的情況了，比如'( ( ( ) ) )'這個(gè)情況，在匹配第一個(gè)右括號的時(shí)候，已經(jīng)知道中間的兩個(gè)括號對的話，則直接跳過，去匹配第六個(gè)做括號，即可得出最長匹配有效括號長度是6。
我們可以嘗試從字符串的末端先提前生成上述兩個(gè)情況的字符串匹配的結(jié)果，首先建立一個(gè)與輸入字符串等長的數(shù)組a，用于保存每個(gè)字符串位置能匹配到的最長的長度，比如對于'( ( ( ) ) )'當(dāng)計(jì)算第一個(gè)右括號的時(shí)候，已經(jīng)知道a[1]的值是4，也就是從這個(gè)位置向右移動(dòng)四個(gè)位置，可以算作第二個(gè)字符的匹配，所以計(jì)算第一個(gè)右括號的話，直接去匹配第五個(gè)。這就是我們要設(shè)計(jì)的動(dòng)態(tài)規(guī)劃的子狀態(tài)了。
這里還有一個(gè)問題，對于'( ( ( ) ) ) ( )'，當(dāng)計(jì)算第一個(gè)的值時(shí)，如果跳過這個(gè)a[1]的值4的長度之后，順利匹配到第五個(gè)字符，而且匹配成功了，但是第五個(gè)字符的后面的字符串依然是一個(gè)匹配完成的字符串，則還要加上這段長度，然后再算作第一個(gè)字符的整體長度
這就是完整的思路了。具體代碼如下：

int longestValidParentheses(const char *s)
{
    int n=strlen(s);
    if(n == 0)
        return 0;
    int i,j;
    int dp[n];
    int max=0;
    
    for(i=0;i<n;i++)
        dp[i]=0;
    for(i=n-2;i>=0;i--)
    {
        if(s[i]=='(')
        {
            j=i+1+dp[i+1];
            if(j<n && s[j]==')')
            {
                dp[i]=dp[i+1]+2;
                if(j+1<n)
                    dp[i]+=dp[j+1];
            }
        }
        if(max<=dp[i])
            max=dp[i];
    }
    return max;
}

思路2:在思路1中我們知道，在一個(gè)括號序列里，當(dāng)遇到一個(gè)左括號')'時(shí)，需要找到其左側(cè)與其最近的右括號'('，而不是最靠前的右括號'('，比如輸入序列'( ( ) )'，很明顯第一個(gè)')'找到的時(shí)候內(nèi)部的右括號'('也就是第二個(gè)右括號'('，而第一個(gè)右括號'('，需要等待其右邊沒有待匹配的右括號'('時(shí)候才開始匹配，針對本例，也就是匹配完內(nèi)部的括號對再匹配外側(cè)的括號對。
那么，當(dāng)我們遇到輸入序列的時(shí)候，如果首先遇到一個(gè)右括號'('，
1、如果其第二個(gè)輸入的是左括號')'，則直接完成匹配；
2、如果其第二個(gè)輸入的依然是右括號'('時(shí)候呢？我們是不是就要把第一個(gè)輸入的右括號'('掛起，等第二個(gè)輸入的右括號'('匹配到后邊的左括號了，再來匹配被掛起的第一個(gè)右括號'('。
遇到這樣的情形，可以將遇到的右括號'('推入棧stack[]數(shù)組中，并記錄stack[top]為輸入序列的索引位置，每遇到一個(gè)左括號')'，則從棧中推出一個(gè)右括號'('。

現(xiàn)在問題來了，我們現(xiàn)在知道如何去找到兩個(gè)匹配的括號了，那么，怎么來計(jì)算最長的有效括號呢，上一步，每一次匹配成功，我們可以獲取到兩個(gè)有效括號對的索引，我們可以新建一個(gè)與輸入字符串等長的mark數(shù)組，每遇到一個(gè)匹配成功的括號對，就將兩個(gè)索引標(biāo)記下來。等循環(huán)遍歷完成，統(tǒng)計(jì)mark數(shù)組的最長連續(xù)標(biāo)記的長度即可。廢話不說了，上代碼。

int longestValidParentheses(char* s) {
    int len=strlen(s);
    if(len <= 1)
        return 0;
    int* mark=(int*)malloc(sizeof(int)*len);
    for(int i=0;i < len;i++)
        mark[i] = -1;
    int* stack=(int*)malloc(sizeof(int)*len);
    int top=0;
    for(int i = 0; i < len; i++){
        if(s[i]=='(')
            stack[top++]=i;
        else{
            if(top!=0){
                mark[stack[top-1]]=0;
                mark[i]=0;
                top--;
              }
          }
    }
          
    int count=0;
    int newCount=0;
    for(int i = 0; i < len;i++){
        if(mark[i]!= -1)
            newCount++;
        else{
            if(newCount>count){
                count=newCount;
            }
            newCount=0;
        }
    }
    if(newCount>count)count=newCount;
    return count;
}

本系列文章，旨在打造LeetCode題目解題方法，幫助和引導(dǎo)同學(xué)們開闊學(xué)習(xí)算法思路，由于個(gè)人能力和精力的局限性，也會(huì)參考其他網(wǎng)站的代碼和思路，如有侵權(quán)，請聯(lián)系本人刪除。