> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/string-match/longest-valid-parentheses.md).

# 32. Longest Valid Parentheses

https\://leetcode.com/problems/longest-valid-parentheses/description/

> Given a string containing just the characters`'('`and`')'`, find the length of the longest valid (well-formed) parentheses substring.
>
> For`"(()"`, the longest valid parentheses substring is`"()"`, which has length = 2.
>
> Another example is`")()())"`, where the longest valid parentheses substring is`"()()"`, which has length = 4.

## Thoughts

由(和)构成的字符串，问能让它们正常配对后最长能有多少。让f\[i]表示以str\[i]为尾的字符串能有的最长合理括号对长度。很明显当str\[i] == '('肯定无法配对。当str\[i]为')'时，最长的长度=被它所形成的括号包住的+在那个括号左边的合法长度。

```cpp
/*
 * @lc app=leetcode id=32 lang=cpp
 *
 * [32] Longest Valid Parentheses
 *
 * https://leetcode.com/problems/longest-valid-parentheses/description/
 *
 * algorithms
 * Hard (26.15%)
 * Likes:    2213
 * Dislikes: 100
 * Total Accepted:    212.3K
 * Total Submissions: 809.8K
 * Testcase Example:  '"(()"'
 *
 * 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 "()()"
 * 
 * 
 */
class Solution {
public:
    int longestValidParentheses(string s) {
        const int N = s.size();
        vector<int> dp(N);
        int res = 0;
        for (int i = 1; i < N; ++i) {
            if (s[i] != ')') continue;
            const int lp =  i - 1 - dp[i - 1];  
            if (lp >= 0 && s[lp] == '(') dp[i] = i - lp + 1 + (lp == 0 ? 0 : dp[lp - 1]);
            res = max(res, dp[i]);
        }
        return res;
    }
};


```