在解决一道莫比乌斯反演时想到的一个问题:
数列 {μ(1),μ(2),...,μ(n)}\{\mu(1),\mu(2),...,\mu(n)\}{μ(1),μ(2),...,μ(n)} 的连续子段和的最大值的量级会是多少?
为了解决这个问题,我写了个程序计算,结果如下:
可以看出,这个量级或许是 O(n)O(\sqrt n)O(n),但我不会证。故来求助各位大佬(虽然我感觉这个问题比 μ\muμ 前缀和的量级还难)。