algorithm - 随机序列的最大连续子序列和的期望

Question

这是 Programming Pearls 第 2 版(第 8.7 章)中的一个问题:

Considering a real number sequence, whose elements are drawn uniformly from the range [-1, 1], what is the expected maximum consecutive subsequence sum? (If all the elements are negative, the maximum sum is 0.)

假设序列的长度是N，是否有一个封闭形式的期望最大子序列和f(N)？我尝试做一些模拟，但没有找到任何线索。

感谢您的帮助。

Answer 1

这类似于 Brownian motion在 1D 中，但步长分布不寻常。对于大 N，它近似于 Wiener process .

(不确定其中任何一项是否有帮助，但如果您不知道其中的联系，它可能会提供额外的查找位置)。