题目描述： 给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”
示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()” 参考官方题解 方法1：动态规划 主要思路： （1）遍历给出的字符串，找出每次以当前的字符向前能获得的最长的长度，取这些获得的最长的长度中的最大值为结果； （2）使用动态数组dp[ i ]表示当前索引 i 下的字符，可以向前组成的最长的长度； （3）通过观察可知，s[ i ]必须为字符 ‘)’ 才可能组成满足要求的字符串，故只需处理 s[i]== ’ ) ’ 的情形，在此情形下，分为以下两种情形讨论： （a）若 s[ i-1] == ‘(’,则说明最后两个字符可以组成一个子字符串，则更向前是否是满足要求的字符串，可以有dp[i-2]知道，故此时dp[i]=dp[i-2]+2;为了避免越界，判断i是否大于2； （b）若s[i-1] != ‘(’,则索引 i 对应的字符要想形成满足要求的字符串，则需要在索引 i-1 对应的字符组成的字符串前面的那个字符是 ‘(’ 才可以，既 s[ i-dp[i-1]-1]==’(’，为了保证不越界，则i-dp[i-1]>0，此时还需要判断索引 i-dp[i-1]-1前面的一个索引 i-dp[i-1]-2可能组成的最大的字符串，故 dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2；为了保证不越界，则需要判断i-dp[i-1]>2； （4）最后使用maxLen来存储所有最大字符串中的最大值；
class Solution { public: int longestValidParentheses(string s) { int maxLen=0; vector<int> dp(s.size(),0); for(int i=1;i<s.size();++i){ if(s[i]==')'){//可能组成满足要求的字符串的情形 if(s[i-1]=='('){ dp[i]=(i>2?dp[i-2]:0)+2; } else if(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('){ dp[i]=dp[i-1]+(i-dp[i-1]>2?dp[i-dp[i-1]-2]:0)+2; } } maxLen=max(maxLen,dp[i]); } return maxLen; } };方法2：使用栈 主要思路： （1）理解在栈底保存之前的最靠后的没有形成满足要求字符串的符号’ ) '的索引，那对于索引 0 来说，其前面一个没有形成满足要求字符串的索引应该是 -1，故将 -1 初始化的压入到栈中；
class Solution { public: int longestValidParentheses(string s) { int maxLen=0; stack<int> st; st.push(-1);//初始化0前面的索引 for(int i=0;i<s.size();++i){ if(s[i]=='('){//将左括号的索引压入到栈中 st.push(i); } else{ st.pop();//是右括号时，将栈中弹出一个元素，表示匹配上了 //若此时栈为空，表示刚弹出的是之前的没有形成满足要求的字符串的右括号的索引 //则此时需要更新新的右括号的索引，故将当前索引压入栈中 if(st.empty()){ st.push(i); } else{ //保存最大值 maxLen=max(maxLen,i-st.top()); } } } return maxLen; } };