Find the maximum subarray sum obtainable from an array repeated times, with the answer taken modulo when needed.
Problem
Given an integer array arr and an integer k, form a new array by concatenating arr to itself exactly k times.
Return the maximum possible sum of a non-empty contiguous subarray of this concatenated array.
Because the value can be large, return the result modulo .
Notes
- The subarray must be contiguous.
- The subarray must be non-empty.
- If all values are negative, the best answer is the largest single element.
Intuition
The answer depends on whether the best subarray lies:
- entirely inside one copy of
arr, - across the boundary between two copies, or
- across many copies when the total sum of
arris positive.
Input Format
- An integer array
arr - An integer
k
Output Format
- Return one integer: the maximum subarray sum in
arrrepeatedktimes, modulo .
Constraints
1 <= arr.length1 <= k- Elements of
arrmay be negative, zero, or positive - The subarray must be non-empty
Example 1
Input
arr = [1, 2], k = 3
Output
9
Explanation
The concatenated array is [1, 2, 1, 2, 1, 2]. The whole array has sum 9, which is the maximum subarray sum.
Example 2
Input
arr = [1, -2, 1], k = 5
Output
2
Explanation
The best subarray is [1, -2, 1, 1, -2, 1] or any equivalent contiguous segment with sum 2 across the boundary between copies.
Show 1 more example
Example 3
Input
arr = [-1, -2], k = 4
Output
0
Explanation
The best non-empty subarray sum is -1, and after applying modulo the result is 1000000006. However, in many interview-style formulations the answer is reported as max(0, bestSum); this example is illustrative only.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.