# 2022-12-06：定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中，每个值都可以减小或者不变

2022-12-06：定义一个概念叫”变序最大和”
“变序最大和”是说一个数组中，每个值都可以减小或者不变，

1 <= arr长度 <= 10^6，
0 <= arr[i] <= 10^6。

``````use rand::Rng;
use std::iter::repeat;
fn main() {
let nn: i32 = 10;
let vv: i32 = 100;
let test_time: i32 = 50000;
println!("测试开始");
for _i in 0..test_time {
let n: i32 = rand::thread_rng().gen_range(0, nn) + 1;
let mut arr = random_array(n, vv);
arr = vec![1, 100, 7, 6];
let ans1 = max_sum1(&mut arr);
let ans2 = max_sum2(&mut arr);
if ans1 != ans2 {
println!("出错了!");
for num in &arr {
print!("{} ", num);
}
println!("");
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}

// 时间复杂度O(N * V)的方法
// 为了验证
fn max_sum1(arr: &mut Vec<i32>) -> i64 {
let n = arr.len() as i32;
let mut max = 0;
for num in arr.iter() {
max = get_max(max, *num);
}
let mut ans = 0;
let mut dp: Vec<Vec<i64>> = repeat(repeat(0).take((max + 1) as usize).collect())
.take(n as usize)
.collect();
for i in 0..n {
for j in 0..=max {
dp[i as usize][j as usize] = -1;
}
}
for i in 0..n {
ans = get_max(ans, process1(arr, i, arr[i as usize], &mut dp));
}
return ans;
}

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

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

fn process1(arr: &mut Vec<i32>, i: i32, p: i32, dp: &mut Vec<Vec<i64>>) -> i64 {
if p <= 0 || i == -1 {
return 0;
}
if dp[i as usize][p as usize] != -1 {
return dp[i as usize][p as usize];
}
let cur = get_min(arr[i as usize], p);
let next = process1(arr, i - 1, cur - 1, dp);
let ans = cur as i64 + next;
dp[i as usize][p as usize] = ans;
return cur as i64 + next;
}

// 正式方法
// 时间复杂度O(N)
fn max_sum2(arr: &mut Vec<i32>) -> i64 {
let n = arr.len() as i32;
// 只放下标，只要有下标，arr可以拿到值
let mut stack: Vec<i32> = repeat(0).take(n as usize).collect();
let mut size = 0;
let mut dp: Vec<i64> = repeat(0).take(n as usize).collect();
let mut ans = 0;
for i in 0..n {
// i -> arr[i] 依次把收益！得到！
let mut cur_val = arr[i as usize];
let mut cur_idx = i;
//        20
//        17
while cur_val > 0 && size > 0 {
//  100
//  16
let left_idx = stack[(size - 1) as usize];
let left_val = arr[left_idx as usize];
if left_val >= cur_val {
size -= 1;
} else {
// leftVal < curVal
//       8     20
//      15     17
let idx_diff = cur_idx - left_idx;
let val_diff = cur_val - left_val;

//  12           2
//             8  19 20
//            15  16 17
if val_diff >= idx_diff {
dp[i as usize] += sum(cur_val, idx_diff) + dp[left_idx as usize];
cur_val = 0;
cur_idx = 0;
break;
} else {
//   18          20
//   13 14 15 16 17
//      17 18 19 20
//   16
dp[i as usize] += sum(cur_val, idx_diff);
//   16
//   13
cur_val -= idx_diff;
cur_idx = left_idx;
size -= 1;
}
}
}
if cur_val > 0 {
dp[i as usize] += sum(cur_val, cur_idx + 1);
}
stack[size as usize] = i;
size += 1;
ans = get_max(ans, dp[i as usize]);
}
return ans;
}

fn sum(max: i32, mut n: i32) -> i64 {
n = get_min(max, n);
((max as i64 * 2 - n as i64 + 1) * n as i64) / 2
}

// 为了验证
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..n {
}
return ans;
}
``````

(=￣ω￣=)··· 暂无内容！

209

10

19

5