【leetcode】Longest Valid Parentheses

 1 class Solution {
 2 public:
 3     int longestValidParentheses(string s) {
 4         int n=s.length();
 5         if(n==0) return 0;
 6        
 7         int *dp=new int[n];
 8         dp[n-1]=0;
 9        
10         int result=0;
11         for(int i=n-2;i>=0;i--)
12         {
13             if(s[i]==‘(‘)
14             {
15                 int j=dp[i+1]+i+1;
16                
17                 if(s[j]==‘)‘)
18                 {
19                     dp[i]=dp[i+1]+2;
20                     if(j<n-1) dp[i]+=dp[j+1];
21                 }
22                 else
23                 {
24                     dp[i]=0;
25                 }
26                
27                 if(dp[i]>result)
28                 {
29                     result=dp[i];
30                 }
31             }
32             else
33             {
34                 dp[i]=0;
35             }
36         }
37         delete [] dp;
38         return result;
39     }
40 };