2022-06-23：给定一个非负数组，任意选择数字，使累加和最大且为7的倍数，返回最大累加和。 n比较大，10的5次方。 来自美团。3.26笔试。

2022-06-23：给定一个非负数组，任意选择数字，使累加和最大且为7的倍数，返回最大累加和。

n比较大，10的5次方。

来自美团。3.26笔试。

答案2022-06-23：

要i还是不要i，递归。可改成动态规划。

代码用rust编写。代码如下：

代码语言：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代码

java rust 递归 动态规划

0 人点赞