第一种方法是dp方法，第二种是利用栈的方法
这道题利用栈的思路很强，虽然普遍都会想到利用栈，但是利用每次进栈的元素来更新空差值，下标之差很精妙，反而dp方法显得不是那么巧妙
万事跪在一个巧字，用下标入栈，秒掉渣渣。
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"Example 2:
Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()" My solution uses DP. The main idea is as follows: I construct a array longest[] , for any longest[i], it stores the longest length of valid parentheses which is end at i. And the DP idea is : If s[i] is '(', set longest[i] to 0,because any string end with '(' cannot be a valid one. Else if s[i] is ')' If s[i-1] is '(', longest[i] = longest[i-2] + 2 Else if s[i-1] is ')' and s[i-longest[i-1]-1] == '(' , longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]For example, input "()(())", at i = 5, longest array is [0,2,0,0,2,0], longest[5] = longest[4] + 2 + longest[1] = 6.
1.
int longestValidParentheses(string s) { if(s.length() <= 1) return 0; int curMax = 0; vector<int> longest(s.size(),0); for(int i=1; i < s.length(); i++){ if(s[i] == ')'){ if(s[i-1] == '('){ longest[i] = (i-2) >= 0 ? (longest[i-2] + 2) : 2; curMax = max(longest[i],curMax); } else{ // if s[i-1] == ')', combine the previous length. if(i-longest[i-1]-1 >= 0 && s[i-longest[i-1]-1] == '('){ longest[i] = longest[i-1] + 2 + ((i-longest[i-1]-2 >= 0)?longest[i-longest[i-1]-2]:0); curMax = max(longest[i],curMax); } } } //else if s[i] == '(', skip it, because longest[i] must be 0 } return curMax; }解释：想找到最大值，无非就是（（））和（）（）类似于这两种，而a[i]只有是‘）’这种才有讨论情况，否则以‘（’为结尾的不存在，也就是0
当a[i]==')',看以a[i-2]为结尾的有多长，longest[i]=longest[i-2] + 2
s[i-longest[i-1]-1] == '('当s[i]是‘）’时，并且s[i-1]是‘）；那么久看以s[i-1]为结尾的有多少，然后减去，i-longest[i-1]-1，看着个是否是‘（’，如果是的话，那就看
i-longest[i-1]-2这个位置的longest，加上就好，前提是i-longest[i-1]-2>0 2. class Solution { public: int longestValidParentheses(string s) { stack<int> stk; stk.push(-1); int maxL=0; for(int i=0;i<s.size();i++) { int t=stk.top(); if(t!=-1&&s[i]==')'&&s[t]=='(') { stk.pop(); maxL=max(maxL,i-stk.top()); } else stk.push(i); } return maxL; } };说明：这个栈存放的是原字符串的下标，t栈顶指针，当栈顶存放的下表t=stack.top(),string[t]为‘（’且a[i]为‘）’，就出栈然后更新max 值，他这个原理是什么呢 就是a[i]和栈顶之间的元素全部出战，i-stack.pop() 比如（（）（（（）））这样的 第一个（入展，然后第二个，紧接着发生配对，pop出来，栈顶元素为小标0，而发生配对现象下表已经到8 2-0=max 6-4=max； 7-3