Longest Valid Parentheses

一个只包含字符 '(' 和字符 ')' 的字符串, 找到最长的有效括号层数

 

my solution

这个问题的核心是如何知道, 哪个 ')' 和哪个 '(' 匹配

这种情况, 如果用栈来解决的话会简单很多

我并没有想到一次循环并找到最大长度的办法

采用的是一次循环将所有能够合并的括号全部替换, 再用一次循环来找到其中最长的序列

效果比想象中的要好, 可能是归功于快速IO

 

the best solution (4ms)

算法给人的第一感觉是"脚印", 如果上一个"脚印"有效, 就加上他, 这样慢慢增加

他也是由两次循环组成, 第一个循环计算每次的步数, 第二次循环找到最大值

规律总结在代码注释, 假设字符串是 "()))()))()", 那么他的 dp 可能是 0 2 0 0 0 2 0 0 0 2

"())(())()()()))" dp 可能是 0 2 0 0 0 2 4 0 6 0 8 0 [10] 0 0

(眼睛有点花... 不过应该没错)

大抵来说:

  1. 跳过了 '(' 的判断, 这会使需要处理的情况少 1/2
  2. 赋值少了 1/2, 他不对 '(' 的索引进行计算

emmm... 学到了很多

感觉"脚印"这个概念在很多算法里面都看到过, 一个个累加将复杂的计算分为了很多的小计算