1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - 动态规划
/// 1. 当k=1时, 问题退化为`53.最大连续子数组和`, 可通过动态规划解决;
/// 2. 当k>1时, 先求出前面2个完整arr组合数组(重复2次)的最大子数组和max_sub_sum;
/// 3. 再计算单个数组arr的总和sum, 如果sum > 0,
/// 可在max_sub_sum后重复串接完整的arr循环得到更大的连续子数组和;
pub fn k_concatenation_max_sum(arr: Vec<i32>, k: i32) -> i32 {
let n = arr.len();
let mut sub_sum = arr[0]; //当前以arr[i]为尾的最大子数组和
let mut max_sub_sum = sub_sum as i64; //最大子数组和
let min_k = k.min(2);
// 前2个重复周期中的最大子数组和
for i in 1..((min_k as usize) * n) {
let i = i % n;
sub_sum = arr[i].max(sub_sum + arr[i]);
max_sub_sum = max_sub_sum.max(sub_sum as i64);
}
// 整个数组和
let sum = arr.iter().clone().sum::<i32>();
// 如果整个数组和>0
if sum > 0 {
// 则可在当个最大和子数组上重复串连完整的数组
max_sub_sum += sum as i64 * ((k - min_k) as i64);
}
if max_sub_sum < 0 {
max_sub_sum = 0;
}
(max_sub_sum % 1000000007_i64) as i32
}
}
// @lc code=end
|