Show problems as
Classic problem #1191MediumArrayDynamic Programming

K-Concatenation Maximum Sum

Real-world version: Best Window Across Repeated Cycles
Tracked in this browser only
Read K-Concatenation Maximum Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A conveyor test rig runs the same programme during every shift. The programme is given as pattern, a list of the net balance changes it records in each of its slots, and the rig runs repeats identical shifts back to back. The full log is therefore pattern written out repeats times in order, so the log holds pattern.length * repeats entries.

A window is a contiguous run of entries of the full log, and its value is the sum of the entries it covers. The empty window is allowed and its value is 0.

Return the largest window value in the full log, taken modulo 1000000007. Compare windows by their exact sums and reduce only the number you return.

Examples

Example 1

Input
pattern = [4, -3, 6], repeats = 3
Output
21

The full log is 4, -3, 6, 4, -3, 6, 4, -3, 6. The window that covers all nine entries has value 21, and 21 modulo 1000000007 is 21.

Example 2

Input
pattern = [-7, -2], repeats = 4
Output
0

Every entry of the log is negative. The empty window is allowed and its value is 0, so 0 is reported.

Example 3

Input
pattern = [5, -11, 5], repeats = 3
Output
10

The full log is 5, -11, 5, 5, -11, 5, 5, -11, 5. The window covering the third and fourth entries has value 10.

Constraints

  • 1 <= pattern.length <= 10^5
  • 1 <= repeats <= 10^5
  • -10^4 <= pattern[i] <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_repeated_window(pattern: list[int], repeats: int) -> int:
Java
public int bestRepeatedWindow(int[] pattern, int repeats)

More on the same topics