1191. K-Concatenation Maximum Sum Medium

1/**
2 * [1191] K-Concatenation Maximum Sum
3 *
4 * Given an integer array arr and an integer k, modify the array by repeating it k times.
5 * For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].
6 * 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.
7 * As the answer can be very large, return the answer modulo 10^9 + 7.
8 *  
9 * Example 1:
10 *
11 * Input: arr = [1,2], k = 3
12 * Output: 9
13 *
14 * Example 2:
15 *
16 * Input: arr = [1,-2,1], k = 5
17 * Output: 2
18 *
19 * Example 3:
20 *
21 * Input: arr = [-1,-2], k = 7
22 * Output: 0
23 *
24 *  
25 * Constraints:
26 *
27 * 1 <= arr.length <= 10^5
28 * 1 <= k <= 10^5
29 * -10^4 <= arr[i] <= 10^4
30 *
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/k-concatenation-maximum-sum/
35// discuss: https://leetcode.com/problems/k-concatenation-maximum-sum/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38use std::cmp;
39impl Solution {
40    const MOD: i128 = 1_000_000_007;
41    pub fn k_concatenation_max_sum(arr: Vec<i32>, k: i32) -> i32 {
42        let c: Vec<i128> = arr.iter().map(|x| *x as i128).collect();
43        let mut two = c.clone();
44        two.append(&mut c.clone());
45        if k == 1 {
46            return (Self::kadane(&c) % Self::MOD) as i32;
47        }
48        (((k - 2) as i128 * cmp::max(0, c.iter().sum()) % Self::MOD
49            + Self::kadane(&two) % Self::MOD)
50            % Self::MOD) as i32
51    }
52
53    fn kadane(input: &Vec<i128>) -> i128 {
54        let mut max = 0;
55        let mut current = 0;
56        for i in input {
57            current = cmp::max(current + *i, *i);
58            max = cmp::max(max, current);
59        }
60        max
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_1191() {
72        assert_eq!(Solution::k_concatenation_max_sum(vec![1, 2], 3), 9);
73    }
74}
75