Leetcode DP3 最长合法括号

题目

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

示例1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

示例2：

Input: ")()(()()())())"
Output: 12
Explanation: The longest valid parentheses substring is "()(()()())()"

问题分解

1. subproblem:每一个合法括号子串都是一个subproblem，计算每一个合法括号子串的长度即可。

2. guess:
   '(' 到下一个点去，因为总有方法能使该'('属于最长合法括号里面。
   ')' 前面的是'('，合法(一种情况)。前面的是')'，则看看前面还有等待结束的'('，有的话就合法，没有的不合法。

3. related:用个table记录下合法子串开始位置到第i处之前的括号的状况(subproblem)。此外还要记录最长长度，也就是每次不合法了，就要刷新一次最长长度。

4. bottom up

5. solve the original problem

代码实现

class Solution {
public:
  int longestValidParentheses(string s) {
        int len = s.length(); 
        if(len<1)   return 0; 
        vector<int > table(len+1,0);//初始化一个table，初始值为0
        int cnt = 0; //cnt就是计数用的，记录有多少个'('等待结束
        if(s[0]=='(')   cnt++;// cnt =1
        else    cnt --; //cnt=-1
        int retMax = 0;
        for(int i=1;i<len;i++){
            if(s[i]=='('){
                if(cnt<0)   cnt=1;
                else    cnt++;
                continue;
            }
            //为')'的情况。
            cnt--;//一个'('被结束了，cnt-=1
            if(cnt>=0){ //cnt>=0的话，就说明前面都是合法的子串，<0的话在下一个i处会进行cnt重置。
                if(s[i-1]=='(') table[i+1] = table[i-1]+2; 
                else{
                    if(s[i-1-table[i]]=='(')
                        table[i+1] = table[i-1-table[i]]+2+table[i];//
                }
                if(retMax<table[i+1])   retMax = table[i+1];
            }
        }
        return retMax;
    }
};