最長有效括弧的問題
作者: Grey
原文地址：最長有效括弧的問題
題目鏈接
主要思路
設置dp數組，長度和原始字元串的長度一樣，
dp[i]表示：必須以i位置字元結尾的字元串的最長有效括弧子串的長度是多少。
顯然有：
dp[0] = 0; // 必須以0位置的字元結尾的最長有效括弧子串是0
dp[1] = (str[1] == ')' && str[0] == '('?2:0); // 必須以1位置的字元結尾的最長有效括弧子串，如果滿足`()`則為2，否則都是無效子串，返回0
然後看任意一個普遍位置i
如果i位置的字元是(，則
dp[i] = 0
因為一個有效的括弧子串的結尾不可能是(
如果i位置的字元是)，則要分以下幾種情況，假設我們以i=6為例，如下示例圖
此時，如果i-1即5位置是(，如下示例
那麼i位置的一種決策是：i位置和i-1先組成一個有效括弧子串，長度是2，然後加上dp[i-2]的值，即：
dp[i] = dp[i-2] + 2
如果i-1位置，即5位置是)，如下示例：
假設dp[i-1]即：dp[5] = 4，即str[2]位置一定是(，如下圖
此時，分兩種情況，如果str[1]位置上是(,即：
那麼此時：
dp[6] = dp[5] + 6位置上的一個右括弧+1位置上的一個左括弧 + dp[0]，即：dp[i] = dp[i-1] + 2 + dp[(i-1) - dp[i-1] - 1]
如果str[1]位置上是)，即：
那麼此時，dp[1]一定等於0，因為如果dp[1]不等於0，那麼就意味著以1結尾的最長有效括弧子串大於0，那麼dp[5]就不止可以擴到2位置了，與我們假設的條件矛盾，所以，當dp[6]為)，且dp[1]為)的時候，dp[6]一定等於0。
自此，所有可能性分析完畢。完整程式碼如下：
public static int longestValidParentheses(String s) {
if (s == null || s.length() <= 1) {
return 0;
}
char[] str = s.toCharArray();
// dp[i]：必須以i位置符號結尾的字元串，最長有效括弧串長度是多少
int[] dp = new int[str.length];
// dp[0] = 0, dp[1] = 0
dp[1] = str[0] == '(' && str[1] == ')' ? 2 : 0;
int ans = dp[1];
for (int i = 2; i < str.length; i++) {
if (str[i] == ')') {
// 這才是有效情況
if (str[i - 1] == '(') {
dp[i] = dp[i - 2] + 2;
} else {
if ((i - 1) - dp[i - 1] >= 0 && str[(i - 1) - dp[i - 1]] == '(') {
dp[i] = dp[i - 1] + 2 + ((i - 1) - dp[i - 1] > 0 ? dp[(i - 1) - dp[i - 1] - 1] : 0);
}
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
