想了半天没想出来,看了题解。
两种解法:
定义Y(i)表示以i为结尾的y的个数,R(i)则表示r的个数。
计算g(x),可以维护y和r的计数器,O(1)就得到。 最小的g(x) 满足x<y,只需要维护当前遇到的g(x)的最小值即可,也是O(1)。
所以整体复杂度O(n),而空间复杂度可以做到O(1)。
自己想时,其实是按照第二种思路来的,但是没有动笔,也缺乏归纳出g(x)的思路,所以没想出来。 而dp也不太熟练,就没法了。
同样是推导,不过用枚举区间的长度,和区间内y的个数做参数,转化为最大连续和问题。
最大连续和问题也是dp。