excelkadanes-algorithm

Finding uninterrupted sub-arrays in Excel - Kadane's algorithm variation?

Suppose you have an ordered, indexed list of positive values. These positive values are interrupted by 0 values. I want to determine if a consecutive sub-array exists which is not interrupted by 0 values and whose sum exceeds a certain threshold.

Simple example:

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

In the above example, the largest consecutive sub-array not interrupted by 0 is from index 2 to index 5 inclusive, and the sum of this sub-array is 15.

Thus, for the following thresholds 20, 10 and 4, the results should be FALSE, TRUE and TRUE respectively.

Note I don't necessarily have to find the largest sub-array, I only have to know if any uninterrupted sub-array sum exceeds the defined threshold.

I suspect this problem is a variation of Kadane's algorithm, but I can't quite figure out how to adjust it.

The added complication is that I have to perform this analysis in Excel or Google Sheets, and I cannot use scripts to do it - only inbuilt formulas.

I'm not sure if this can even be done, but I would be grateful for any input.

Solution

  • Start with

    =B2

    in c2

    then put

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

    in C3 and copy down.

    enter image description here

    EDIT 1

    If you were looking for a Google sheets solution, try something like this:

    =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)))

    Assumes that numbers in column B start with zero: would need to add Iferror if not. It's basically an array formula implementation of @Gary's student's method.

    EDIT 2

    Here is the Google Sheets formula translated back into Excel. It gives you an alternative if you don't want to use 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))))))

    (entered as an array formula).

    Comment

    Maybe the real challenge is to find a formula that works both in Excel and Google sheets because: