2022-12-06：定义一个概念叫“变序最大和“ “变序最大和“是说一个数组中，每个值都可以减小或者不变， 在必须把整体变成严格升序的情况下，得到的最大累加和 比如，[1,100,7] 变成 [1,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 {        ans.push(rand::thread_rng().gen_range(0, v));    }    return ans;}