这是 Programming Pearls 第 2 版(第 8.7 章)中的一个问题:
考虑一个实数序列,它的元素是从 range 中均匀抽取的
[-1, 1]
,预期的最大连续子序列总和是多少?(如果所有元素都是负数,则最大和为0
。)
假设序列的长度为N
,是否存在预期最大子序列总和的封闭形式f(N)
?我尝试做一些模拟,但没有找到任何线索。
感谢帮助。
这是 Programming Pearls 第 2 版(第 8.7 章)中的一个问题:
考虑一个实数序列,它的元素是从 range 中均匀抽取的
[-1, 1]
,预期的最大连续子序列总和是多少?(如果所有元素都是负数,则最大和为0
。)
假设序列的长度为N
,是否存在预期最大子序列总和的封闭形式f(N)
?我尝试做一些模拟,但没有找到任何线索。
感谢帮助。
执行多次模拟并保存所有结果。将它们放入直方图中,您会看到某些值具有更频繁出现的属性。由于随机性,您必须执行大量测试,以便您的直方图变得更加可靠(即使那样我也不确定结果的公平性)。
这个问题在Quora也有提交。链接在这里
其中一个回复是关于模拟的:
以下是一些小案例的确切答案,由 Mathematica 提供。不幸的是,在这些之后计算变得非常慢。
In[1]:= f[n_] := Expectation[Max[0, Max[Table[Sum[x[k], {k, i, j}], {i, n}, {j, i, n}]]], Distributed[Table[x[i], {i, n}], UniformDistribution[Table[{-1, 1}, {n}]]]]
In[2]:= Table[f[n], {n, 5}]
Out[2]= {1/4, 1/2, 23/32, 291/320, 4141/3840}