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]为')'时，最长的长度=被它所形成的括号包住的+在那个括号左边的合法长度。

/*
 * @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;
    }
};