2022-07-03：数组里有0和1，一定要翻转一个区间，翻转：0变1，1变0。 请问翻转后可以使得1的个数最多是多少？ 来自小红书。3.13笔试。

答案2022-07-03：

某个区间，0个数-1个数=最大值。 0变成1，1变成-1，求子数组的最大累加和。

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

use rand::Rng;
fn main() {
    let nn: i32 = 100;
    let test_time: i32 = 20000;
    println!("测试开始");
    for i in 0..test_time {
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let mut arr = random_array(n);
        let mut arr2 = arr.clone();
        let ans1 = max_one_numbers1(&mut arr);
        let ans2 = max_one_numbers2(&mut arr2);
        if ans1 != ans2 {
            println!("出错了!{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

fn max_one_numbers1(arr: &mut Vec<i32>) -> i32 {
    let mut ans = 0;
    for l in 0..arr.len() as i32 {
        for r in l..arr.len() as i32 {
            reverse(arr, l, r);
            ans = get_max(ans, one_numbers(arr));
            reverse(arr, l, r);
        }
    }
    return ans;
}

fn reverse(arr: &mut Vec<i32>, l: i32, r: i32) {
    for i in l..=r {
        arr[i as usize] ^= 1;
    }
}

fn one_numbers(arr: &mut Vec<i32>) -> i32 {
    let mut ans = 0;
    for num in arr.iter() {
        ans += *num;
    }
    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn max_one_numbers2(arr: &mut Vec<i32>) -> i32 {
    let mut ans = 0;
    for num in arr.iter() {
        ans += *num;
    }
    for i in 0..arr.len() as i32 {
        arr[i as usize] = if arr[i as usize] == 0 { 1 } else { -1 };
    }
    let mut max = -2147483648;
    let mut cur = 0;
    for i in 0..arr.len() as i32 {
        cur += arr[i as usize];
        max = get_max(max, cur);
        cur = if cur < 0 { 0 } else { cur };
    }
    return ans + max;
}

// 为了测试
fn random_array(n: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, 2));
    }
    return arr;
}

执行结果如下：

在这里插入图片描述

左神java代码