求O(n)时间复杂度下的最大归一化均值子数组

这是最大和子数组问题的变体（类似固定大小k的最大平均子数组问题），核心目标是找到归一化均值（计算公式：sum/√length）最大的子数组，而非传统的最大和子数组。

示例对比 #

给定数组：c(1, -3, -4, 2, 6, 8, -4, -3, -5, 1, 7, -9, 3, 2)

• 传统最大和子数组为c(2,6,8)，最大和为16，可通过Kadane算法在O(n)时间求解；
• 本问题的最优子数组为c(6,8)，对应的最大归一化均值为9.899495。

当前进展 #

已实现O(n²)复杂度的解法，但需要找到O(n)时间复杂度的高效解法。尝试修改Kadane算法但未得到准确结果，现使用R语言进行模拟测试：

set.seed(1) # 测试时尝试过seed 1到20进行对比
n=30000
z <- rnorm(n)
normalized_mean_subarray(z)

理想输出 #

输出需包含：最大归一化均值、对应子数组的起止索引；仅输出最大值也可接受。

参考解法补充 #

O(n²)参考解法的测试结果：当n=2000、set.seed(1)时，最大归一化均值为4.171375，对应子数组索引为1270-1295。

内容的提问来源于stack exchange，提问作者timxymo1225