DP：最长有效括号

问题：

思路1：DP（时间：O（n）;空间：O(n )）

设DP[i]表示以下标i的半括号结尾的最长有效括号长度。设s为字符串，s[i]只能为)才能结尾，否则DP[i]=0。
当s[i]=)且s[i-1]=(时，dp[i]=dp[i-2]+2。
当s[i]=)且s[i-1]=)时，则在前面必有一个(与s[i]对应，它的位置在s[ i-1-DP[i-1] ]。因此当s[i]=)且s[i-1]=)且s[ i-1-DP[i-1] ]=(时：
DP[i]=DP[i-1]+2+DP[ i-1-DP[i-1]-1 ]
需注意最后一项，它表示将与s[i]对应的左括号之前已存在的有效括号加上

初始时将DP数组初始化为0，需注意前两个字符的特殊情况，当s[0]=(且s[1]=)时，需将dp[1]设为2，否则dp[1]在之后的循环中不会更新

代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int n=s.size();
        int i;
        int* dp;
        dp=( int* )malloc( n*sizeof( int ) );
        if( s.size()<=1 )
            return 0;
        int maxx=0; 
        for( i=0;i<n;i++ )
            dp[i]=0;  
        if( s[0]=='(' && s[1]==')' )
        {
            dp[1]=2;
            maxx=max( maxx,dp[1] );
        }   
        for( i=0;i<n;i++ )
        {
            if( i-1>=0 && s[i]==')' && s[i-1]=='(' )
            {
                if( i-2>=0 )
                {
                    dp[i]=dp[i-2]+2;
                    maxx=max( maxx,dp[i] );
                }
            }
            else if( i-1>=0 && s[i]==')' && s[i-1]==')' )
            {
                if( i-dp[i-1]-1>=0 && s[ i-dp[i-1]-1 ]=='(' )
                {   
                    dp[i]=dp[i-1]+2;
                    if( i-dp[i-1]-2>=0 )
                        dp[i]+=dp[ i-dp[i-1]-2 ];
                    maxx=max( maxx,dp[i] );
                }
            }
        }
        return maxx;
    }
};

思路2：栈（时间：O（n）;空间：O(n )）

由于只需求最长有效括号串的长度，因此我们只需将下标入栈。我们的想法是：每遇到左括号，将其入栈，每遇到右括号，将栈顶左括号出栈，根据它的下标计算有效括号串长度，即当前下标-出栈元素下标+1
考虑以下情况：

我们会发现一个问题：遍历到下标为5的元素时，计算出的长度为5-2+1=4，最前面的两个元素不在栈中，被忽略掉了；

我们需要最前面的括号串留下它的痕迹，为此我们需要修改计算有效括号串长度的规则，我们需要将每个有效括号串前面的一个字符作为标识压入栈中

我们引入垫底下标解决该问题，在初始栈时将-1 push进去，计算长度的规则变为：当前下标-出栈后的栈顶元素下标。

垫底下标是需要更换的，当栈中只有一个元素，即垫底元素时，若当前遍历到的为)，如下标为6的元素，表示前面的有效字符串已结束，此时将当前下标作为垫底元素压入栈中

代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push( -1 );
        int n=s.size();
        int maxx=0;
        int i;
        for( i=0;i<n;i++ )
        {
            if( s[i]=='(' )
            {
                st.push( i );
            }
            else
            {
                if( st.top()==-1 || s[ st.top() ]==')' )
                {
                    st.pop();
                    st.push( i );
                }
                else
                {
                    st.pop();
                    maxx=max( maxx,i-st.top() );
                }
            }
        }
        return maxx;
    }
};

思路3：双向扫描记录左右括号个数（时间：O（n）;空间：O(1) ）

对于每个有效括号串，其左括号个数一定等于右括号个数。我们用left记录左括号个数，用right记录右括号个数，从左到右遍历字符串，若右括号个数已经大于左括号个数，则不可能构成有效括号串，将left和right赋为0。若left==right，则更新最长括号串长度

但这样我们会发现一个问题，若左括号数大于右括号数，但已经不可能成为有效括号串的情况，如(()，我们从左到右遍历时会认为它仍有可能成为有效括号，因此无法排除这种情况

因此我们再进行反向遍历解决该问题，不过反向遍历时，若左括号数已经大于右括号数，将left和right重置为0

代码：

class Solution {
public:
    int longestValidParentheses(string s) {
        int left=0;
        int right=0;
        int i;
        int maxx=0;
        int n=s.size();
        for( i=0;i<n;i++ )
        {
            if( s[i]=='(' )
            {
                left++;
            }
            else
            {
                right++;
            }
            if( left<right )
            {   
                left=0;
                right=0;
            }
            else if( left==right )
            {
                maxx=max( left+right,maxx );
            }
        }
        left=0;
        right=0;
        for( i=n-1;i>=0;i-- )
        {
            if( s[i]=='(' )
            {
                left++;
            }
            else
            {
                right++;
            }
            if( left>right )
            {   
                left=0;
                right=0;
            }
            else if( left==right )
            {
                maxx=max( left+right,maxx );
            }
        }
        return maxx;
    }
};