Find the maximum subarray sum obtainable from an array repeated times, with the answer taken modulo when needed.
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 .
The answer depends on whether the best subarray lies:
arr,arr is positive.arrkarr repeated k times, modulo .1 <= arr.length1 <= karr may be negative, zero, or positiveExample 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.
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
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.