# 32. Longest Valid Parentheses

## 刷题内容

• https://leetcode.com/problems/longest-valid-parentheses/

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 "()()"


˼·1 **- ʱ�临�Ӷ�: O(n)*- �ռ临�Ӷ�: O(n)***

��DP�ķ内容描述⡣������һ��ջȥ内容描述��ߵĲ��֣���'('��λ�ã�ֱ内容描述һ��')'ʱ���ͼ�¼ջ����'('λ�ã内容描述��ǾͿ���д��״̬ת�Ʒ��̡内容描述�dp[i]�����ַ����е�i内容描述����Զ��λ�á�����һ������')'ʱ��dp[i] = ջ��'('��λ�á����ڿ��Դ内容描述����ţ���dp[dp[i] - 1]���ڣ���dp[i] = dp[dp[i] - 1]����Ҫע��߽缴�ɡ�

class Solution {
public:
int longestValidParentheses(string s) {
int len = s.length();
if(!len)
return 0;
int dp[len];
memset(dp,-1,sizeof(dp));
int ans = 0;
vector<int> v;
for(int i = 0;i < len;++i)
if(s[i] == '(')
v.push_back(i);
else if(s[i] == ')' && v.size())
{
dp[i] = v[v.size() - 1];
if(dp[i] && dp[dp[i] - 1] >= 0)
dp[i] = dp[dp[i] - 1];
ans = max(ans,i - dp[i] + 1);
v.pop_back();
}
return ans;
}
};