C++刷leetcode(32. 最长有效括号)【动态规划】

糖逗

题目描述：

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std; 


int longestValidParentheses(string s) {
    int len = s.size();
    if(len < 2) return 0;
    vector<int> dp(len, 0);
    for(int i = 1; i < len; i++){
        if(s[i] == ')'){
            if(s[i-1] == '('){
                int temp = i-2 >= 0 ? dp[i-2] : 0;
                dp[i] = temp+2;
            }
            else{
                if(i-dp[i-1]-1 >= 0&&s[i-dp[i-1]-1] == '('){
                    int temp = i-dp[i-1]-2 >=0 ? dp[i-dp[i-1]-2] : 0;
                    dp[i] = temp + dp[i-1] + 2;
                }
            }
        }

    }
    return *max_element(dp.begin(), dp.end());
}


int main(void){
        string input;
        cin >> input;
        cout << longestValidParentheses(input) << endl;
        return 0;
}