Предположим, у вас есть упорядоченный индексированный список положительных значений. Эти положительные значения прерываются значениями 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
соответственно.
Примечание. Мне не обязательно искать самый большой подмассив, мне нужно только знать, превышает ли какая-либо непрерывная сумма подмассива определенный порог.
Я подозреваю, что эта проблема является разновидностью алгоритма Кадане, но я не могу понять, как его настроить.
Дополнительная сложность заключается в том, что я должен выполнять этот анализ в Excel или Google Sheets, и я не могу использовать для этого сценарии — только встроенные формулы.
Я не уверен, что это можно сделать, но я был бы признателен за любой вклад.