1191. K-Concatenation Maximum Sum

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 <= 105`
• `1 <= k <= 105`
• `-104 <= arr[i] <= 104`

Rust Solution

``````struct 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);
}
``````

Having problems with this solution? Click here to submit an issue on github.