Longest Valid Parentheses

given a string containing just the

characters <code>‘(‘</code> and <code>‘)‘</code>, find the length

of the longest valid (well-formed) parentheses substring.

for <code>"(()"</code>, the longest valid parentheses substring

is <code>"()"</code>, which has length = 2.

another example is <code>")()())"</code>, where the longest valid

parentheses substring is <code>"()()"</code>, which has length = 4.

也就是說要找到最長的子串滿足比對規則。

算法思路，建立兩個數組pre[]和post[],生成規則如下：

pre數組：從前向後周遊原字元串s，若該下标i所對應的字元為‘(‘，則

：(1)若i為0，pre[i]=1;(2)若pre[i-1]&lt;0,pre[i]=1(3)其餘情況，pre[i]=pre[i-1]+1;

post數組：從後向前周遊原字元串s，若該下标i所對應的字元為‘)‘，則：(1)若i為s.length-1，post[i]=1;(2)若post[i+1]&lt;0,pre[i]=1(3)其餘情況，pre[i]=pre[i+1]+1;

例如：字元串")()())"的pre數組為 -1  1  0  1  0  -1，post數組為2

 1  2  1  2  1

然後在pre數組中從後向前找到第一個值為0的下标，若沒有，則從pre數組中找出的最長子串為0，若找到，再向前找出第一個小于0的下标，或者全部大于0，此時下标遞減到0，則從pre數組中找出的最長子串的長度就是這兩個下标的內插補點。

同理，在post數組中從前向後找第一個值為0的下标，然後再找第一個值小于0的下标或者下标到s.length-1，從post數組中找到的子串長度即這兩個下标的內插補點。

是以，滿足條件的最長子串的長度就是從pre數組和post數組中找到的長度的最大值。

因為算法中周遊了兩次原字元串，一次pre數組和一次post數組，是以時間複雜度為o(n)，空間複雜度為兩個數組pre和post，為o(n)

////////////////////////////////////////////////////////////////////////////////////////////分割線/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

看了一下網上的做法，轉載一下：

轉自

這道題可以用一維動态規劃逆向求解。假設輸入括号表達式為string s，維護一個長度為s.length的一維數組dp[]，數組元素初始化為0。

dp[i]表示從s[i]到s[s.length -

1]包含s[i]的最長的有效比對括号子串長度。則存在如下關系：

dp[s.length - 1] = 0;

i從n - 2 -&gt; 0逆向求dp[]，并記錄其最大值。若s[i] == ‘(‘，則在s中從i開始到s.length -

1計算dp[i]的值。這個計算分為兩步，通過dp[i + 1]進行的（注意dp[i + 1]已經在上一步求解）：

在s中尋找從i + 1開始的有效括号比對子串長度，即dp[i + 1]，跳過這段有效的括号子串，檢視下一個字元，其下标為j = i

+ 1 + dp[i + 1]。若j沒有越界，并且s[j] == ‘)’，則s[i ... j]為有效括号比對，dp[i] =dp[i + 1] +

2。

在求得了s[i ... j]的有效比對長度之後，若j + 1沒有越界，則dp[i]的值還要加上從j +

1開始的最長有效比對，即dp[j + 1]。