Longest Valid Parentheses

Problem: Longest Valid Parentheses

If there are l length long valid parentheses before a ")" and before these valid parentheses lies a "(", we can extend l to l + 2. If there are exactly x valid parentheses before the "(", we can extend the answer to l+2+x.

Code in Python:

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        arr = [0]*(n+1)
        for i in xrange(1,n+1):
            if arr[i] == 0 and s[i-1] == ')':
                l = i-arr[i-1]-1
                if l > 0 and s[l-1] == '(':
                    arr[i] = arr[i-1] +2
            if arr[i] != 0:
                arr[i] += arr[i-arr[i]]
        return max(arr)

Code in Java:

public class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            if (arr[i] == 0 && s.charAt(i-1) == ')') {
                int l = i-arr[i-1]-1;
                if (l > 0 && s.charAt(l-1) == '(')
                    arr[i] = arr[i-1]+2;
            }
            if (arr[i] != 0)
                arr[i] += arr[i-arr[i]];
        }

        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            res = Math.max(res, arr[i]);
        }
        return res;
    }
}