题解|#32. 最长有效括号#

方法1

此种方***导致内存溢出或超时

从(开始计数，匹配到(加1，匹配到)减1.
计数清零后，循环下一个索引
返回最大值

方法2

由于括号是连续的，因此当前位置的最长有效长度是和前面有关的。可以使用动态规划

如果当前是(，则当前位置有效长度为0。dp[i] = 0
如果当前是)
- 如果前一位是(，正好组成一个匹配的括号。dp[i] = dp[i-1] + 2
  
  注意，i-2可能越界
- 如果前一位是)，则寻找去除前一位最长匹配后的左侧，是不是(，如果是，正好和当前位组成一个有效括号。
```
 val index = i - 1 - dp[i-1]
 if (index >= 0 && '(' == s[index]) {
     // "()(())" ; 此处要加开头的两个括号
     dp[i] = dp[i-1] + 2 + if (index-1 > 0)dp[index - 1] else 0
 } else {
     dp[i] = 0
 }
```
  注意index和index-1可能越界
找到所有dp中，最长的一个，即为结果

方法2代码实现

import org.junit.Test
import java.util.concurrent.atomic.AtomicInteger

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionLongestValidParentheses {
    @Test
    fun main() {
        println(longestValidParentheses("()(())"))
        println(longestValidParentheses("()"))
        // println(longestValidParentheses(")()())"))
        // println(longestValidParentheses(""))
        println(longestValidParentheses("())"))
        println(longestValidParentheses("(()())"))
        // println(longestValidParentheses(")(((((()())()()))()(()))("))
        // println(longestValidParentheses("((())())(()))(()()(()(()))(()((((()))))))((()())()))()()(()(((((()()()())))()())(()()))((((((())))((()))()()))))(()))())))()))()())((()()))))(()(((((())))))()((()(()(())((((())(())((()()(()())))())(()(())()()))())(()()()))()(((()())(((()()())))(((()()()))(()()))()))()))))))())()()((()(())(()))()((()()()((())))()(((()())(()))())())))(((()))))())))()(())))()())))())()((()))((()))()))(((())((()()()(()((()((())))((()()))())(()()(()))))())((())))(()))()))))))()(()))())(()())))))(()))((())(()((())(((((()()()(()()())))(()())()((()(()()))(()(())((()((()))))))))(()(())()())()(()(()(()))()()()(()()())))(())(()((((()()))())))(())((()(())())))))())()()))(((())))())((()(()))(()()))((())(())))))(()(()((()((()()))))))(()()()(()()()(()(())()))()))(((()(())()())(()))())))(((()))())(()((()))(()((()()()(())()(()())()(())(()(()((((())()))(((()()(((()())(()()()(())()())())(()(()()((()))))()(()))))(((())))()()))(()))((()))))()()))))((((()(())()()()((()))((()))())())(()((()()())))))))()))(((()))))))(()())))(((()))((()))())))(((()(((())))())(()))))(((()(((((((((((((())(((()))((((())())()))())((((())(((())))())(((()))))()())()(())())(()))))()))()()()))(((((())()()((()))())(()))()()(()()))(())(()()))()))))(((())))))((()()(()()()()((())((((())())))))((((((()((()((())())(()((()))(()())())())(()(())(())(()((())((())))(())())))(()()())((((()))))((()(())(()(()())))))))))((()())()()))((()(((()((()))(((((()()()()()(()(()((()(()))(()(()((()()))))()(()()((((((()((()())()))((())()()(((((()(()))))()()((()())((()())()(())((()))()()(()))"))
        // println(longestValidParentheses(")(()(()(((())(((((()()))((((()()(()()())())())()))()()()())(())()()(((()))))()((()))(((())()((()()())((())))(())))())((()())()()((()((())))))((()(((((()((()))(()()(())))((()))()))())"))
        // val s = "((((()())()()))()(()))"
        // if((((()())()()))()(()))
        // println(s.length)
        // println(longestValidParentheses(s))
        //

    }

    fun longestValidParentheses(s: String): Int {
        if ("".equals(s)) {
            return 0
        }
        if (s.length < 2) {
            return 0
        }
        if ("()" == s) {
            return 2
        }
        // 第i个最长的有效字符 ，最大：从第i开始，往前计算
        // 此种推断 ，dp[i] 都是从最右开始的有效
        val dp = IntArray(s.length + 1)
        // dp[0] = 0
        var max = 0
        for (i in 1 until s.length) {
            // dp[i] =
            if (')' == s[i] && '(' == s[i - 1]) {
                // a()
                // 第i位及之前组成一个括号
                val index = i - 2
                if (index >= 0) {
                    dp[i] = dp[index] + 2
                } else {
                    dp[i] = 2
                }
            } else if (')' == s[i]) {
                // 前一位也是 )，判断前一位最长有效后的左边一个是不是 (
                // "())" 导致越界
                // i-1 为左边一个); dp[i-1] 为左边一个(的最长有效长度
                val index = i - 1 - dp[i-1]
                if (index >= 0 && '(' == s[index]) {
                    // "()(())" ; 此处要加开头的两个括号
                    dp[i] = dp[i-1] + 2 + if (index-1 > 0)dp[index - 1] else 0
                } else {
                    dp[i] = 0
                }
            } else {
                dp[i] = 0
            }
            max = max.coerceAtLeast(dp[i])
        }
        return max
        TODO()
    }

}
//leetcode submit region end(Prohibit modification and deletion)