Leetcode 32 Longest Valid Parentheses

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution 1: Use DP. dp[i] is when current length is i and use last character to form longest valid parentheses. Most difficult part is the character is ')'. Use"...()(())" as example, the blue part is dp[i-1], if the one before blue part (one with underscore) is open parentheses, then we can form a longer one dp[i-1]+2. It is not end here. Before the underscore, if there is another valid parentheses (pink one), we can combine together to form a even longer one.

 public class Solution {  
   public int longestValidParentheses(String s) {  
     int n=s.length(), res=0;  
     if (n==0) return 0;  
     int[] dp=new int[n];  
     for (int i=0; i<n; i++) {  
       if (s.charAt(i)==')') {  
         if (i>0 && i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1)=='(') {  
           dp[i]=dp[i-1]+2;  
           if (i-dp[i]>=0) dp[i]+=dp[i-dp[i]];  
           res=Math.max(res,dp[i]);  
         }  
       }  
     }  
     return res;  
   }  
 }