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.