对于这个题，暴力解法就不说了。首先讲一下动态规划的方法，如1所示，我们用dp[i]来记录前i个字符中的最长有效括号数。我们可以发现，在遍历s时，只有当前元素为“）”时才有可能更新dp的值，否则保持不变。当遍历到某个元素位“）”时，我们要寻找在它之前的可以刚好与其配对的“（”，目前有两种情况，如果前一个元素是“（”，那么dp[i]的值可以直接加2，如果不是，那么就要考察前一个元素“）”所在的位置的dp值，并找到该“）”对应的最长序列的前一个元素，如果是”（“，我们才能将dp[i]加2，但是此时考虑到如果我们加上被新形成的括号所包含的最长括号序列，我们就要将改值加到dp[i]上。在寻找i所在位置的“）”前一个所对应的“（”要注意，不能使得i小于0，否则会跑到列表的末尾，这样大概率会得到一个错误答案。除此之外，尽管我们在算dp[i]时加上了新产生的括号对中所包含的最长序列的值，我们并没有加上与新产生的括号对的并列且在新产生的括号对之外的序列，因为有可能由于形成新括号对，有可能讲两个分离的有效括号序列给连接了起来，我们也要加上这种情况，于是dp[i]要加上dp[i-dp[i-1]-2]。最终就完成了状态更新。这种方法的时间复杂度是O（N），空间复杂度是O（N）。
除了第一种方法之外，还有一种更加节省空间的做法。就是正向，反向分别遍历一遍s。在正向遍历的时候，我们要同时用left和right记录下左右括号的数量，当left和right相等时，更新答案maxlength，maxlength为当前maxlength和两倍的left（或right）的数量中的较大值。注意有一种特殊情况，就是当一个多余的“）”隔断了序列，因为前面没有足够的”（“与之对应，这种情况下我们要将left和right都重置为0，但是这样带来的结果是当出现类似“（（）”的情况时，我们永远没法计算出一个序列长度（因为left和right的值永远不会相等了）。这就是为什么我们要重新换个方向从右往左遍历序列，并且此时应该在出现多余的”（“时将left和right重置为0，这样就能找到最终的答案。注意到我们在换方向遍历之前要首先将left和right重置回0。这个方法的时间复杂度为O（N），空间复杂为O（1）。
python:
class Solution:
def longestValidParentheses1(self, s: str) -> int:
size = len(s)
if size == 0:
return 0
dp = [0]*size
for i in range(size):
if s[i] == ")" and i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == "(":
dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
return max(dp)
def longestValidParentheses2(self, s: str) -> int:
maxlength, size, left, right = 0, len(s), 0, 0
for i in range(size):
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
maxlength = max(maxlength, 2 * left)
elif right > left:
left, right = 0, 0
left, right = 0, 0
for i in range(size-1, -1, -1):
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
maxlength = max(maxlength, 2 * left)
elif left > right:
left, right = 0, 0
return maxlength