excel - 在 Excel 中查找不间断的子数组 - Kadane 的算法变体？

Question

假设您有一个有序的、索引的正值列表。这些正值被 0 值中断。我想确定是否存在不被 0 值中断且总和超过某个阈值的连续子数组。

简单的例子:

Index, Value
0   0
1   0
2   3
3   4
4   2
5   6
6   0
7   0
8   0
9   2
10  3
11  0

在上面的例子中，未被0中断的最大连续子数组来自索引 2索引 5包含，这个子数组的和是 15 .

因此，对于以下阈值 20 , 10和 4 ，结果应该是 FALSE , TRUE和 TRUE分别。

注意我不一定要找到最大的子数组，我只需要知道是否有任何不间断的子数组总和超过定义的阈值。

我怀疑这个问题是 Kadane 算法的变体，但我不太清楚如何调整它。

增加的复杂性是我必须在 Excel 或 Google 表格中执行此分析，并且我不能使用脚本来执行此操作 - 只能使用内置公式。

我不确定这是否可以做到，但我将不胜感激任何意见。

Answer 1

从...开始

=B2

在c2

然后放

=IF(B3=0,0,B3+C2)

在 C3 中并复制下来。



编辑 1

如果您正在寻找 Google 表格解决方案，请尝试以下操作:

=ArrayFormula(max(sumif(A2:A,"<="&A2:A,B2:B)-vlookup(A2:A,{if(B2:B=0,A2:A),sumif(A2:A,"<="&A2:A,B2:B)},2)))

假设 B 列中的数字从零开始:如果不是，则需要添加 Iferror。它基本上是@Gary 的学生方法的数组公式实现。

编辑 2

这是翻译回 Excel 的 Google 表格公式。如果您不想使用 Offset，它为您提供了另一种选择:

=MAX(SUMIF(A2:A13,"<="&A2:A13,B2:B13)-INDEX(SUMIF(A2:A13,"<="&A2:A13,B2:B13),N(IF({1},MATCH(A2:A13,IF(B2:B13=0,A2:A13)))))) 

(作为数组公式输入)。

评论

也许真正的挑战是找到一个适用于 Excel 和 Google 表格的公式，因为:

Vlookup 在 Excel 中的工作方式不同

偏移量/小计组合在 Google 表格中不起作用

带有 n(if{1}... 的索引/匹配组合在 Google 表格中不起作用。