solved 'Longest Valid Parentheses' on LeetCode https://leetcode.com/problems/longest-valid-parentheses/

longest_paren.cc

class Solution {
public:
    int longestValidParentheses(string s) {
      int sz = s.size();
      // Records for DP, `longest[i]` is the max number
      // of pairs of brackets ending with `s[i-1]`.
      vector<int> longest(sz + 1, 0);
      int max_pairs = 0;
      for (int i = 1; i < sz; ++i) {
        if (s[i] == '(') {
          // Opening, can't be valid.
          longest[i + 1] = 0;
        } else {
          int before = i - 1 - longest[i] * 2;
          if (before < 0 || s[before] != '(') {
            // No opening bracket to close.
            longest[i + 1] = 0;
          } else {
            // Close one and connect with previous longest sequence.
            longest[i + 1] = longest[i] + 1 + (before < 0 ? 0 : longest[before]);
          }
        }

        // Record the maximum.
        if (longest[i + 1] > max_pairs) {
          max_pairs = longest[i + 1];
        }
      }
      return max_pairs * 2;
    }      
};