非负一维数组求和超阈值的最小区间求解算法咨询

需求为针对元素均为非负整数或浮点数的一维数组x，寻找满足x[start:end].sum() > threshold的最短切片，支持可选约束：start <= argmax(x) < end，即返回的区间必须包含数组最大值的位置。
现有自实现版本运行速度未达预期，要求实现方案不引入numba这类重型依赖。

测试示例 #

x = [0, 1, 2, 3, 4, 9, 7, 1, 0, 0, 0]
threshold = 3 + 4 + 9 + 7 - .01

start, end = func(x, threshold)
print(x[start:end])

预期输出：

[3, 4, 9, 7]

补充要求 #

• 优先选择无numba依赖的实现，尽可能减少显式if分支、for循环的使用
• 若存在足够轻量的numba替代加速方案也可接受

由于数组元素全为非负值，该场景存在线性时间复杂度的成熟解法，不需要重型JIT依赖：

• 无「必须包含最大值位置」约束的场景：直接使用经典滑动窗口（双指针）算法即可，时间复杂度O(n)，空间复杂度O(1)。非负特性保证了右指针右移时区间和单调递增、左指针右移时区间和单调递减，仅需单次遍历即可找到所有满足和要求的区间，同步更新最短区间长度即可。
• 带「必须包含最大值位置」约束的场景：
  1. 首先单次遍历找到数组最大值所在位置m = argmax(x)
  2. 初始化窗口左右边界均为m，初始窗口和为x[m]，初始化最短区间的起止位置
  3. 之后循环向左右两侧扩展窗口：每一步比较左边界左侧相邻值、右边界右侧相邻值的大小，优先向值更大的一侧扩展，同步累加窗口和，直到窗口和大于阈值即可停止。该贪心策略成立的核心原因是元素非负，要让包含固定点m的区间以最短长度达到和阈值，永远优先选择新增贡献更大的一侧扩展即可，全程时间复杂度同样为O(n)。

如果需要进一步提升性能，可以基于numpy做向量化实现——numpy属于Python数值计算的基础轻量依赖，远轻于numba，可将显式循环、分支的开销降低1~2个数量级，完全可以满足性能要求。

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