Given an integer array arr and an integer k, modify the array by repeating it k times.
For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.
As the answer can be very large, return the answer modulo 109 + 7.
Example 1:
Input: arr = [1,2], k = 3 Output: 9
Example 2:
Input: arr = [1,-2,1], k = 5 Output: 2
Example 3:
Input: arr = [-1,-2], k = 7 Output: 0
Constraints:
1 <= arr.length <= 1051 <= k <= 105-104 <= arr[i] <= 104struct Solution;
const MOD: i32 = 1_000_000_007;
impl Solution {
fn k_concatenation_max_sum(arr: Vec<i32>, k: i32) -> i32 {
let sum: i32 = arr.iter().sum();
let mut prev = 0;
let mut res = 0;
let mut k = k as usize;
let n = arr.len();
for i in 0..n * k.min(2) {
prev = arr[i % n].max(prev + arr[i % n]);
res = res.max(prev);
}
while sum > 0 && k > 2 {
res += sum;
res %= MOD;
k -= 1
}
res
}
}
#[test]
fn test() {
let arr = vec![1, 2];
let k = 3;
let res = 9;
assert_eq!(Solution::k_concatenation_max_sum(arr, k), res);
let arr = vec![1, -2, 1];
let k = 5;
let res = 2;
assert_eq!(Solution::k_concatenation_max_sum(arr, k), res);
let arr = vec![-1, -2];
let k = 7;
let res = 0;
assert_eq!(Solution::k_concatenation_max_sum(arr, k), res);
}