Best k days on a repeating roster

Scenario

A ride-hailing app plans a repeating driver roster of n days. After the last day of the roster, it starts again from the first day. For each roster day, the app knows how many trips are usually completed.

A driver can take any k days in a row of the roster, and the stretch may wrap from the end of the roster back to the start. You are asked for the highest number of trips over any such stretch. The best stretch for the total is also the best for the average, because the length is always k.

Your task

Write best_wrapped_total(trips, k).

trips[i] is the usual number of trips on roster day i. The roster has n = trips.length days and repeats: after day n - 1 comes day 0.
A stretch is k days in a row, starting at any roster day. It may wrap around the end.
Return the highest total number of trips over any stretch. Its average is this total divided by k.
k is at least 1 and at most n.

Examples

Example 1 (traced)#

text2 lines

Input:  trips = [9, 1, 2, 3, 4, 8], k = 3
Output: 21

The first window is days 0 to 2: 9 + 1 + 2 = 12. Each slide drops the day that leaves, trips[start - 1], and adds the day that enters, trips[(start + k - 1) % n]. The % wraps the index.

start	Leaves	Enters	Window total	best after
0			12	12
1	9	3	6	12
2	1	4	9	12
3	2	8	15	15
4	3	9 (day 0, wrapped)	21	21
5	4	1 (day 1, wrapped)	18	21

The best stretch is days 4, 5 and 0: 4 + 8 + 9 = 21.

Example 2#

text2 lines

Input:  trips = [4, 4, 4], k = 3
Output: 12

The stretch is the whole roster, 4 + 4 + 4.

Example 3#

text2 lines

Input:  trips = [7], k = 1
Output: 7

One day is a stretch of one day.

Constraints

1 ≤ trips.length ≤ 100,000 (days in the roster)
0 ≤ trips[i] ≤ 10^6 (trips per day)
1 ≤ k ≤ trips.length

What does n ≤ 10^5 tell you?

Adding up the k days of every stretch from scratch costs about n × k steps. With n = 100,000 and k = 50,000 that is 5 × 10^9: about 50 seconds at 10^8 operations a second. Sliding the window costs n steps, 100,000 in all.

A total can reach 100,000 × 10^6 = 10^11. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).

Scenario

Your task

Write best_wrapped_total(trips, k).

trips[i] is the usual number of trips on roster day i. The roster has n = trips.length days and repeats: after day n - 1 comes day 0.
A stretch is k days in a row, starting at any roster day. It may wrap around the end.
Return the highest total number of trips over any stretch. Its average is this total divided by k.
k is at least 1 and at most n.

Examples

Example 1 (traced)#

text2 lines

Input:  trips = [9, 1, 2, 3, 4, 8], k = 3
Output: 21

The first window is days 0 to 2: 9 + 1 + 2 = 12. Each slide drops the day that leaves, trips[start - 1], and adds the day that enters, trips[(start + k - 1) % n]. The % wraps the index.

start	Leaves	Enters	Window total	best after
0			12	12
1	9	3	6	12
2	1	4	9	12
3	2	8	15	15
4	3	9 (day 0, wrapped)	21	21
5	4	1 (day 1, wrapped)	18	21

The best stretch is days 4, 5 and 0: 4 + 8 + 9 = 21.

Example 2#

text2 lines

Input:  trips = [4, 4, 4], k = 3
Output: 12

The stretch is the whole roster, 4 + 4 + 4.

Example 3#

text2 lines

Input:  trips = [7], k = 1
Output: 7

One day is a stretch of one day.

Constraints

1 ≤ trips.length ≤ 100,000 (days in the roster)
0 ≤ trips[i] ≤ 10^6 (trips per day)
1 ≤ k ≤ trips.length

What does n ≤ 10^5 tell you?

A total can reach 100,000 × 10^6 = 10^11. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).