2022-06-23：给定一个非负数组，任意选择数字，使累加和最大且为7的倍数，返回最大累加和。
n比较大，10的5次方。
来自美团。3.26笔试。
答案2022-06-23：
要i还是不要i，递归。可改成动态规划。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let len: i32 = 12;
let value: i32 = 100;
let test_time: i32 = 10000;
println!("测试开始");
for i in 0..test_time {
let n = rand::thread_rng().gen_range(0, len) + 1;
let mut arr = random_array(n, value);
let ans1 = max_sum1(&mut arr);
let ans2 = max_sum2(&mut arr);
if ans1 != ans2 {
println!("出错了!{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
fn max_sum1(arr: &mut Vec<i32>) -> i32 {
return process1(arr, 0, 0);
}
fn process1(arr: &mut Vec<i32>, index: i32, pre: i32) -> i32 {
if index == arr.len() as i32 {
return if pre % 7 == 0 { pre } else { 0 };
}
let p1 = process1(arr, index + 1, pre);
let p2 = process1(arr, index + 1, pre + arr[index as usize]);
return get_max(p1, p2);
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn max_sum2(arr: &mut Vec<i32>) -> i32 {
if arr.len() == 0 {
return 0;
}
let n = arr.len() as i32;
let mut dp: Vec<Vec<i32>> = vec![];
for i in 0..n {
dp.push(vec![]);
dp[i as usize].push(0);
for _ in 1..7 {
dp[i as usize].push(-1);
}
}
dp[0][(arr[0] % 7) as usize] = arr[0];
for i in 1..n {
// 当前arr[i] % 7 的余数
let cur_mod = arr[i as usize] % 7;
for j in 0..7 {
dp[i as usize][j as usize] = dp[(i - 1) as usize][j as usize];
let find_mod = (7 - cur_mod + j) % 7;
if dp[(i - 1) as usize][find_mod as usize] != -1 {
dp[i as usize][j as usize] = get_max(
dp[i as usize][j as usize],
dp[(i - 1) as usize][find_mod as usize] + arr[i as usize],
);
}
}
}
return if dp[(n - 1) as usize][0] == -1 {
0
} else {
dp[(n - 1) as usize][0]
};
}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _i in 0..n {
arr.push(rand::thread_rng().gen_range(0, v) + 1);
}
return arr;
}
执行结果如下：
左神java代码
