2022-07-29：一共有n个人，从左到右排列，依次编号0~n-1， h[i]是（腾讯代号N）

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

执行结果如下：