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

2022-12-06：定义一个概念叫”变序最大和”
“变序最大和”是说一个数组中，每个值都可以减小或者不变，
在必须把整体变成严格升序的情况下，得到的最大累加和
比如，[1,100,7]变成[1,6,7]时，就有变序最大和为14
比如，[5,4,9]变成[3,4,9]时，就有变序最大和为16
比如，[1,4,2]变成[0,1,2]时，就有变序最大和为3
给定一个数组arr，其中所有的数字都是>=0的。
求arr所有子数组的变序最大和中，最大的那个并返回。
1 <= arr长度 <= 10^6，
0 <= arr[i] <= 10^6。
来自Amazon。

答案2022-12-06：

单调栈+dp。
时间复杂度：O(N)。
空间复杂度：O(N)。

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

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;
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接