2022-06-17：给定一个数组arr，含有n个数字，可能有正、有负、有0，
给定一个正数k。
返回所有子序列中，累加和最大的前k个子序列累加和。
假设K不大，怎么算最快？
来自Amazon。
答案2022-06-17：
排序，小根堆。
代码用rust编写。代码如下：
fn main() {
let mut nums: Vec = vec![6, 19, 3, 8, 29];
let ans = top_max_sum2(&mut nums, 3);
println!("ans = {:?}", ans);
}
fn top_max_sum2(arr: &mut Vec, k: i32) -> Vec {
let mut sum = 0;
for i in 0..arr.len() as i32 {
if arr[i as usize] >= 0 {
sum += arr[i as usize];
} else {
arr[i as usize] = -arr[i as usize];
}
}
let mut ans = top_min_sum(arr, k);
for i in 0..ans.len() as i32 {
ans[i as usize] = sum - ans[i as usize];
}
return ans;
}
fn top_min_sum(arr: &mut Vec, k: i32) -> Vec {
arr.sort();
// (最右的下标，集合的累加和)
let mut heap: Vec> = vec![];
heap.push(vec![0, arr[0]]);
let mut ans: Vec = vec![];
for _ in 0..k {
ans.push(0);
}
// ans[0] = 0
// 0 1 2 k-1
// k个！
for i in 1..k {
heap.sort_by(|a, b| b[1].cmp(&a[1]));
let cur = heap.pop().unwrap();
// (7, 100)
// 左 ：8, 100 - arr[7] + arr[8]
// 右 ：8， 100 + arr[8]
let last = cur[0];
let sum = cur[1];
ans[i as usize] = sum;
if last + 1 < arr.len() as i32 {
heap.push(vec![
last + 1,
sum - arr[last as usize] + arr[(last + 1) as usize],
]);
heap.push(vec![last + 1, sum + arr[(last + 1) as usize]]);
}
}
return ans;
}
执行结果如下：
左神java代码
