本文共 1231 字，大约阅读时间需要 4 分钟。

题目链接为

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.

这道题可以用动态规划来解决

class Solution {public:    int longestValidParentheses(string s) {        int len = s.length();        int *dp = new int[len + 1];        int max = 0;        dp[0] = 0;        dp[1] = 0;        for(int i = 1; i < len; i++){            if(s[i]==')'){                if(s[i-1]=='('){                    dp[i+1] = dp[i-1] + 2;                }                else{                    int last = i-dp[i];                    if(last > 0 && s[last-1]=='('){                        dp[i+1] = dp[last-1] + dp[i] + 2;                    }                    else {                        dp[i+1] = 0;                    }                }            }            else {                dp[i+1] = 0;            }        }        for(int i = 1; i <= len; i++){            max = max > dp[i] ? max : dp[i];        }        return max;    }};

转载地址：https://blog.csdn.net/qq_30306087/article/details/78156654 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！