P100 有效括号的最大长度

描述#

这个题目说的是，给你一个包含左括号和右括号的字符串，你要找到能形成有效括号组合的最长子串，然后返回它的长度。

比如说，给你的括号字符串是：
) ( ( ) ( ) )
这个字符串，从下标 1 开始，一直到最后，都是一个有效的括号组合，因此你要返回长度 6。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int maxLengthOfValidParenthesesStack(String s) {
    if (s == null || s.length() == 0) return 0;
    int n = s.length(), p = -1, max = 0;
    int[] st = new int[n+1];
    st[++p] = -1;

    for (int i = 0; i < n; ++i) {
      if (st[p] != -1 && s.charAt(st[p]) == '(' && s.charAt(i) == ')') {
        --p;
        max = Math.max(max, i - st[p]);
      } else st[++p] = i;
    }
    return max;
  }

  // Time: O(n), Space: O(n)
  public int maxLengthOfValidParenthesesDP(String s) {
    if (s == null || s.length() == 0) return 0;
    int n = s.length(), left = 0, max = 0;
    int[] d = new int[n];

    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '(') {
        ++left;
      } else if (left > 0) {
        d[i] = d[i-1] + 2;
        d[i] += (i - d[i]) >= 0 ? d[i-d[i]] : 0;
        max = Math.max(max, d[i]);
        --left;
      }
    }
    return max;
  }

}