2022-07-29：一共有n个人，从左到右排列，依次编号0~n-1， h[i]是第i个人的身高， v[i]是第i个人的分数， 要求从左到右选出一个子序列，在这个子序列中的人，从左到右身高是不下降的。

2022-07-29：一共有n个人，从左到右排列，依次编号0~n-1，
h[i]是第i个人的身高，
v[i]是第i个人的分数，
要求从左到右选出一个子序列，在这个子序列中的人，从左到右身高是不下降的。
返回所有符合要求的子序列中，分数最大累加和是多大。
n <= 10的5次方, 1 <= h[i] <= 10的9次方, 1 <= v[i] <= 10的9次方。
来自字节。

答案2022-07-29：

线段树。

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

use rand::Rng;

fn main() {

    let nn: i32 = 30;

    let vv: i32 = 100;

    let test_time: i32 = 20000;

    println!("测试开始");

    for _ in 0..test_time {

        let n = rand::thread_rng().gen_range(0, nn) + 1;

        let mut h = random_array(n, vv);

        let mut v = random_array(n, vv);

        if right(&mut h, &mut v) != max_sum(&mut h, &mut v) {

            println!("出错了!");

            break;

        }

    }

    println!("测试结束");

}

// 为了测试

// 绝对正确的暴力方法

fn right(h: &mut Vec<i32>, v: &mut Vec<i32>) -> i32 {

    return process(h, v, 0, 0);

}

fn process(h: &mut Vec<i32>, v: &mut Vec<i32>, index: i32, pre_value: i32) -> i32 {

    if index == h.len() as i32 {

        return 0;

    }

    let p1 = process(h, v, index + 1, pre_value);

    let p2 = if h[index as usize] >= pre_value {

        v[index as usize] + process(h, v, index + 1, h[index as usize])

    } else {

        0

    };

    return get_max(p1, p2);

}

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

    if a > b {

        a

    } else {

        b

    }

}

// 正式方法

// 时间复杂度O(N * logN)

fn max_sum(h: &mut Vec<i32>, v: &mut Vec<i32>) -> i32 {

    let n = h.len() as i32;

    let mut rank0 = h.clone();

    rank0.sort();

    let mut st = SegmentTree::new(n);

    for i in 0..n {

        let height = rank(&mut rank0, h[i as usize]);

        // 1~height max

        let t = st.max1(height);

        st.update1(height, t + v[i as usize]);

    }

    return st.max1(n);

}

// [150, 152, 160, 175]  160

//   1    2    3    4

// 3

fn rank(rank0: &mut Vec<i32>, num: i32) -> i32 {

    let mut l = 0;

    let mut r = rank0.len() as i32 - 1;

    let mut m = 0;

    let mut ans = 0;

    while l <= r {

        m = (l + r) / 2;

        if rank0[m as usize] >= num {

            ans = m;

            r = m - 1;

        } else {

            l = m + 1;

        }

    }

    return ans + 1;

}

pub struct SegmentTree {

    pub n: i32,

    pub max: Vec<i32>,

    pub update: Vec<i32>,

}

impl SegmentTree {

    pub fn new(max_size: i32) -> Self {

        let n = max_size + 1;

        let mut max: Vec<i32> = vec![];

        let mut update: Vec<i32> = vec![];

        for _ in 0..n << 2 {

            max.push(0);

            update.push(-1);

        }

        Self { n, max, update }

    }

    pub fn update1(&mut self, index: i32, c: i32) {

        self.update0(index, index, c, 1, self.n, 1);

    }

    pub fn max1(&mut self, right: i32) -> i32 {

        return self.max0(1, right, 1, self.n, 1);

    }

    fn push_up(&mut self, rt: i32) {

        self.max[rt as usize] = get_max(

            self.max[(rt << 1) as usize],

            self.max[(rt << 1 | 1) as usize],

        );

    }

    fn push_down(&mut self, rt: i32, _ln: i32, _rn: i32) {

        if self.update[rt as usize] != -1 {

            self.update[(rt << 1) as usize] = self.update[rt as usize];

            self.max[(rt << 1) as usize] = self.update[rt as usize];

            self.update[(rt << 1 | 1) as usize] = self.update[rt as usize];

            self.max[(rt << 1 | 1) as usize] = self.update[rt as usize];

            self.update[rt as usize] = -1;

        }

    }

    fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {

        if ll <= l && r <= rr {

            self.max[rt as usize] = cc;

            self.update[rt as usize] = cc;

            return;

        }

        let mid = (l + r) >> 1;

        self.push_down(rt, mid - l + 1, r - mid);

        if ll <= mid {

            self.update0(ll, rr, cc, l, mid, rt << 1);

        }

        if rr > mid {

            self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);

        }

        self.push_up(rt);

    }

    fn max0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {

        if ll <= l && r <= rr {

            return self.max[rt as usize];

        }

        let mid = (l + r) >> 1;

        self.push_down(rt, mid - l + 1, r - mid);

        let mut ans = 0;

        if ll <= mid {

            ans = get_max(ans, self.max0(ll, rr, l, mid, rt << 1));

        }

        if rr > mid {

            ans = get_max(ans, self.max0(ll, rr, mid + 1, r, rt << 1 | 1));

        }

        return ans;

    }

}

// 为了测试

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) + 1);

    }

    return ans;

}

执行结果如下：

左神java代码

2022-07-29：一共有n个人，从左到右排列，依次编号0~n-1， h[i]是第i个人的身高， v[i]是第i个人的分数， 要求从左到右选出一个子序列，在这个子序列中的人，从左到右身高是不下降的。的相关教程结束。