XL Web

← All challenges

Circular Array Maximum Sum

Array & Sequence ★★☆☆

Maximum sum of any contiguous subarray over a 24-hour cycle of net cash flows, where the window may wrap from end-of-day back to start-of-day.

A1:A24 records the net cash flow per hour at a 24/7 store, hour 1 through hour 24 of a single day. Some hours are profitable; the early-afternoon dead zone bleeds money.

You want to identify the best contiguous window of consecutive hours to keep the registers open, where the day is treated as a cycle — a window may begin late in the evening and continue past midnight into the next morning. Return the maximum total cash flow of any such window.

The classic non-circular Kadane gets the best non-wrapping window, but the optimal here genuinely wraps midnight, so the formula must handle both cases.

Input

Range A1:A24

A
1 16
2 17
3 29
4 29
5 33
6 35
7 13
8 10
9 -3
10 11
11 -6
12 -36
13 -39
14 -42
15 -46
16 -16
17 -37
18 -32
19 -10
20 21
21 12
22 34
23 29
24 27
Hint

Two cases: (a) the answer is a non-wrapping subarray — Kadane's max. (b) the answer wraps — that's TOTAL minus the minimum-sum non-wrapping subarray. Take the larger.

Solution 
=LET(
  arr, A1:A24,
  kadane_max, MAX(SCAN(0, arr, LAMBDA(s,c, MAX(c, s+c)))),
  kadane_min, MIN(SCAN(0, arr, LAMBDA(s,c, MIN(c, s+c)))),
  total, SUM(arr),
  MAX(kadane_max, total - kadane_min)
)