32. Longest Valid Parentheses

Let dp[i] be the longest valid parentheses at position i (Note, it is not the longest valid parentheses from the beginning). We are going to face following cases:

Case 1: s[i] == '('
It is invalid, so dp[i] = 0.

Case 2: s[i] == ')'
If s[i-1] == '(', then dp[i] = dp[i-2] + 2;
Else (i.e. s[i-1] == ')'), since dp[i-1] is records the longest valid parentheses, we only need to check if the parentheses at position i-dp[i-1]-1 is '('. If so, dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2].

At the end, we pick the longest one from dp[i].

1:  class Solution {  
2:  public:  
3:    int longestValidParentheses(string s) {  
4:      if (s.size() < 2) return 0;  
5:      vector<int> dp(s.size(), 0);  
6:      for (int i = 1; i < s.size(); i++) {  
7:        if (s[i] == ')') {  
8:          if (s[i-1] == '(') {  
9:            dp[i] = i-2 >= 0 ? dp[i-2] + 2 : 2;  
10:          } else {  
11:            if (i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(') {  
12:              dp[i] = dp[i-1] + 2 + (i-dp[i-1]-2 >= 0 ? dp[i-dp[i-1]-2] : 0);  
13:            }  
14:          }  
15:        }  
16:      }  
17:      int max_l = 0;  
18:      for (int i = 0; i < s.size(); i++) {  
19:        max_l = max(max_l, dp[i]);  
20:      }  
21:      return max_l;  
22:    }  
23:  };