2022-07-03：数组里有0和1，一定要翻转一个区间，翻转：0变1，1变0。
请问翻转后可以使得1的个数最多是多少？
来自小红书。3.13笔试。
答案2022-07-03：
某个区间，0个数-1个数=最大值。
0变成1，1变成-1，求子数组的最大累加和。
代码用rust编写。代码如下：
代码语言：javascript复制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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_04_3_week/Code01_MaxOneNumbers.java)
