2022-06-17：给定一个数组arr，含有n个数字，可能有正、有负、有0，给定一个正数k。返回所有子序列中，累加和最大的前k个子序列累加和。假设K不大

原创

福大大架构师每日一题

发布于 2022-06-17 22:52:15

4940

发布于 2022-06-17 22:52:15

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-06-17：给定一个数组arr，含有n个数字，可能有正、有负、有0，

给定一个正数k。

返回所有子序列中，累加和最大的前k个子序列累加和。

假设K不大，怎么算最快？

来自Amazon。

答案2022-06-17：

排序，小根堆。

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

fn main() {
    let mut nums: Vec<i32> = vec![6, 19, 3, 8, 29];
    let ans = top_max_sum2(&mut nums, 3);
    println!("ans = {:?}", ans);
}

fn top_max_sum2(arr: &mut Vec<i32>, k: i32) -> Vec<i32> {
    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<i32>, k: i32) -> Vec<i32> {
    arr.sort();
    // (最右的下标，集合的累加和)
    let mut heap: Vec<Vec<i32>> = vec![];
    heap.push(vec![0, arr[0]]);
    let mut ans: Vec<i32> = 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;
}

执行结果如下：