在 Excel 中查找不间断的子数组 - Kadane 的算法变体？
Finding uninterrupted sub-arrays in Excel - Kadane's algorithm variation?
假设您有一个有序的索引正值列表。这些正值被 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 表格中执行此分析，而且我不能使用脚本来执行此操作 - 只能使用内置公式。
我不确定这是否可以完成，但如果有任何意见，我将不胜感激。
使用列 A 和 B 中的数据，确保列 B 以 0 结尾.然后在C2中输入：
=IF(AND(B3=0,B2<>0),SUM(B$1:$B2)-MAX($C$1:C1),"")
并向下复制：
列 C 列出了连续非零的总和。在另一个单元格中输入如下内容：
=MAX(C:C)>19
其中 19 是条件值。
您可以使用 VBA UDF 来避免 "helper" 列。
编辑#1：
改用这个：
=IF(AND(B3=0,B2<>0),SUM(B:$B2)-SUM($C:C1),"")
开始于
=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
这里是 Google 表格公式转换回 Excel。如果您不想使用 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
中的工作方式不同
- offset/subtotal 组合在 Google 张中不起作用
- index/match 与 n(if{1}... 的组合在 Google 工作表中不起作用。
感谢@Tom Sharpe 和@Gary 的学生回答问题。
虽然我承认没有在问题中指定这一点，但我更愿意在没有辅助列的情况下实现解决方案，因为我必须在 30 多个连续的列上执行此操作。我只是认为在 Excel.
中不可能
Full credit goes to user XOR LX on the Excelforum for coming up with this solution。它让我大吃一惊，花了我一个多小时的时间来思考，但它确实很有创意。我不可能自己想出办法。 Re-posting 在这里是为了让所有正在研究这个的人受益。
将我最初问题中的 table 复制并粘贴到一个空的 Excel sheet 中，这样 headers 就会出现在 (A1:B1) 中，并且值会出现在 (A2:B13).
然后把这个公式作为数组公式输入(ctrl+shift+enter)，给出所有不间断的总和的最大值sub-arrays:
=MAX(SUBTOTAL(9,OFFSET(B2,A2:A14,,-FREQUENCY(IF(B2:B13,A2:A13),IF(B3:B14=0,A2:A13,0))-1)))
请注意故意偏移以在数据集末尾下方包含一个额外的行。
假设您有一个有序的索引正值列表。这些正值被 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 表格中执行此分析，而且我不能使用脚本来执行此操作 - 只能使用内置公式。
我不确定这是否可以完成，但如果有任何意见，我将不胜感激。
使用列 A 和 B 中的数据，确保列 B 以 0 结尾.然后在C2中输入：
=IF(AND(B3=0,B2<>0),SUM(B$1:$B2)-MAX($C$1:C1),"")
并向下复制：
列 C 列出了连续非零的总和。在另一个单元格中输入如下内容：
=MAX(C:C)>19
其中 19 是条件值。
您可以使用 VBA UDF 来避免 "helper" 列。
编辑#1：
改用这个：
=IF(AND(B3=0,B2<>0),SUM(B:$B2)-SUM($C:C1),"")
开始于
=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
这里是 Google 表格公式转换回 Excel。如果您不想使用 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 中的工作方式不同
- offset/subtotal 组合在 Google 张中不起作用
- index/match 与 n(if{1}... 的组合在 Google 工作表中不起作用。
感谢@Tom Sharpe 和@Gary 的学生回答问题。
虽然我承认没有在问题中指定这一点，但我更愿意在没有辅助列的情况下实现解决方案，因为我必须在 30 多个连续的列上执行此操作。我只是认为在 Excel.
中不可能Full credit goes to user XOR LX on the Excelforum for coming up with this solution。它让我大吃一惊，花了我一个多小时的时间来思考，但它确实很有创意。我不可能自己想出办法。 Re-posting 在这里是为了让所有正在研究这个的人受益。
将我最初问题中的 table 复制并粘贴到一个空的 Excel sheet 中，这样 headers 就会出现在 (A1:B1) 中，并且值会出现在 (A2:B13).
然后把这个公式作为数组公式输入(ctrl+shift+enter)，给出所有不间断的总和的最大值sub-arrays:
=MAX(SUBTOTAL(9,OFFSET(B2,A2:A14,,-FREQUENCY(IF(B2:B13,A2:A13),IF(B3:B14=0,A2:A13,0))-1)))
请注意故意偏移以在数据集末尾下方包含一个额外的行。