解题思路
本题的本质是求执行过程中,同时嵌套的有效 O(n) 循环的最大层数。
一层循环若执行 n 次,相当于在当前复杂度上乘一个 n。例如当前复杂度为 ncur,再进入一层执行 n 次的循环后,复杂度变为 ncur×n=ncur+1,所以令 cur+1;常数次循环只乘一个常数,不影响指数。若某层循环一次也不执行,则它内部的代码也不会执行,因此这些内部循环都不能产生复杂度贡献。
由于 END 总是结束最近的 FOR,使用栈模拟循环嵌套。维护 cur 表示当前有效的 O(n) 循环层数,ans 表示最大的 cur,bad 表示当前处于多少层不执行的循环中。
栈中用 3 种状态表示当前 FOR: