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

糖逗

题目描述：

1. 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: "(()"
   
6. 输出: 2
   
7. 解释: 最长有效括号子串为 "()"
   
8. 示例 2:
   
9. 
   
10. 输入: ")()())"
    
11. 输出: 4
    
12. 解释: 最长有效括号子串为 "()()"
    
13. 
    
14. 来源：力扣（LeetCode）
    
15. 链接：https://leetcode-cn.com/problems/longest-valid-parentheses
    
16. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. 
   
7. 
   
8. int longestValidParentheses(string s) {
   
9.     int len = s.size();
   
10.     if(len < 2) return 0;
    
11.     vector<int> dp(len, 0);
    
12.     for(int i = 1; i < len; i++){
    
13.         if(s[i] == ')'){
    
14.             if(s[i-1] == '('){
    
15.                 int temp = i-2 >= 0 ? dp[i-2] : 0;
    
16.                 dp[i] = temp+2;
    
17.             }
    
18.             else{
    
19.                 if(i-dp[i-1]-1 >= 0&&s[i-dp[i-1]-1] == '('){
    
20.                     int temp = i-dp[i-1]-2 >=0 ? dp[i-dp[i-1]-2] : 0;
    
21.                     dp[i] = temp + dp[i-1] + 2;
    
22.                 }
    
23.             }
    
24.         }
    
25. 
    
26.     }
    
27.     return *max_element(dp.begin(), dp.end());
    
28. }
    
29. 
    
30. 
    
31. int main(void){
    
32.         string input;
    
33.         cin >> input;
    
34.         cout << longestValidParentheses(input) << endl;
    
35.         return 0;
    
36. }
    
37. 
    

复制代码