LC32. 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.
找到最长的可行括号组成，用DP来解应该就可以。dp[i]存i结尾的最长可行子序列长度，用栈存”(“的位置，如果遇到一个”)”,就更新当前位置的值。这种“(())”对应dp[stack.pop() - 1], “()”对应dp[i-1], 其中有一个为0.
public class Solution {
public int longestValidParentheses(String s) {
if(s == null || s.length() < 2) return 0;
int len = s.length();
int[] dp = new int[len]; // longest valid end with i
Stack<Integer> stack = new Stack<Integer>();
int max = 0;
for(int i = 0; i < dp.length; i++){
if(s.charAt(i) == '('){
stack.push(i);
}else if(s.charAt(i) == ')'){
if(stack.isEmpty()) continue;
else if(stack.peek() > 0){
dp[i] = 2 + dp[stack.pop() - 1] + dp[i-1];
}else{
dp[i] = 2 + dp[i-1];
stack.pop();
}
}
max = Math.max(max, dp[i]);
}
return max;
}
}
O(n), O(n)