2022-06-23: given a nonnegative array, select any number to make the maximum cumulative sum a multiple of 7, and return the maximum cumulative sum. N is larger, to the 5th power of 10. From meituan. 3

2022-06-23： Given a nonnegative array , Select any number , Make the sum of accumulation maximum and equal to 7 Multiple , Returns the maximum cumulative sum .

n The larger ,10 Of 5 Power .

From meituan .3.26 written examination .

answer 2022-06-23：

want i Or not i, recursive . It can be changed into dynamic programming .

The code to use rust To write . The code is as follows ：

use rand::Rng;
fn main() {
    let len: i32 = 12;
    let value: i32 = 100;
    let test_time: i32 = 10000;
    println!(" Beginning of the test ");
    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!(" Something went wrong !{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!(" End of test ");
}

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 {
        //  At present arr[i] % 7  The remainder of 
        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]
    };
}

//  In order to test 
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;
}

Copy

The results are as follows ：

Insert picture description here

Zuo Shen java Code