LeetCode_32_LongestValidParentheses
题目分析：
其实这题并没有用上平衡括号特性，只是一个以平衡括号为载体的dp题。
算是个收集癖写在这里。但是记得这跟平衡括号，其实没啥特别关系。
要用上dp了。子串常见的定义法。就是另dp[i]为
"以i为结尾"
"以i为结尾"
"以i为结尾"
的子串的对应结果。
方程
1.s[i]如果是左括号，一个左括号结尾自然是0。
2.s[i]如果是右括号
就看在dp[i - 1]的"对称位置"是否是左括号
int pre = i - dp[i - 1] - 1;//对称
2.1如果不是，一个右括号结尾，就是0。
2.2如果是
if(pre >= 0 && chas[pre] == '(')
长度就扩充2。并且！！！如果pre不是开始位置，加上dp[pre - 1]。
为了这种情况 ()(()) 续上之前的子串。
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
解法：
public static int longestValidParentheses2(String s) {
/**
* 动态规划，dp[i]为以s[i]为结尾的最长有效字串长度
* s[i]=='('，dp[i]为零
* s[i]=')',看对称位置是否为'(',注意()(()),这种情况，前面也得加上
* 和我想法一样 但是没有写下去 凸(艹皿艹 )
*/
char[] chas = s.toCharArray();
int[] dp = new int[chas.length];
int res = 0;
for(int i = 1; i < chas.length; i++){
if(chas[i] == ')'){
int pre = i - dp[i - 1] - 1;//对称
if(pre >= 0 && chas[pre] == '('){
/**
* pre > 0 ? dp[pre - 1] : 0
* 解决了 ()(()) 这种情况的连接问题
*/
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
res = Math.max(res, dp[i]);
}
return res;
}