Find the K-Sum of an Array

class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        long long maxSum = 0;
        for (int& x : nums) {
            if (x > 0) maxSum += x;
            else x = -x;
        }
        sort(nums.begin(), nums.end());
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
        pq.push({0, 0});
        long long loss = 0;
        for (int i = 0; i < k - 1; ++i) {
            auto [l, idx] = pq.top(); pq.pop();
            loss = l;
            if (idx < (int)nums.size()) {
                pq.push({l + nums[idx], idx + 1});
                if (idx > 0) pq.push({l + nums[idx] - nums[idx - 1], idx + 1});
            }
        }
        return maxSum - loss;
    }
};

import (
    "container/heap"
    "sort"
)

type pair struct {
    loss int64
    idx  int
}
type minHeap []pair

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i].loss < h[j].loss }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *minHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func kSum(nums []int, k int) int64 {
    var maxSum int64 = 0
    for i, x := range nums {
        if x > 0 {
            maxSum += int64(x)
        } else {
            nums[i] = -x
        }
    }
    sort.Ints(nums)
    pq := &minHeap{}
    heap.Push(pq, pair{0, 0})
    var loss int64 = 0
    for i := 0; i < k-1; i++ {
        top := heap.Pop(pq).(pair)
        loss = top.loss
        if top.idx < len(nums) {
            heap.Push(pq, pair{top.loss + int64(nums[top.idx]), top.idx + 1})
            if top.idx > 0 {
                heap.Push(pq, pair{top.loss + int64(nums[top.idx]) - int64(nums[top.idx-1]), top.idx + 1})
            }
        }
    }
    return maxSum - loss
}

import heapq
from typing import List

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        max_sum = 0
        for i, x in enumerate(nums):
            if x > 0:
                max_sum += x
            else:
                nums[i] = -x
        nums.sort()
        pq: List[tuple] = [(0, 0)]
        loss = 0
        for _ in range(k - 1):
            l, idx = heapq.heappop(pq)
            loss = l
            if idx < len(nums):
                heapq.heappush(pq, (l + nums[idx], idx + 1))
                if idx > 0:
                    heapq.heappush(pq, (l + nums[idx] - nums[idx - 1], idx + 1))
        return max_sum - loss

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0, n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

var kSum = function(nums, k) {
    let maxSum = 0n;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) maxSum += BigInt(nums[i]);
        else nums[i] = -nums[i];
    }
    nums.sort((a, b) => a - b);
    const pq = new MinHeap();
    pq.push([0n, 0]);
    let loss = 0n;
    for (let i = 0; i < k - 1; i++) {
        const [l, idx] = pq.pop();
        loss = l;
        if (idx < nums.length) {
            pq.push([l + BigInt(nums[idx]), idx + 1]);
            if (idx > 0) pq.push([l + BigInt(nums[idx]) - BigInt(nums[idx - 1]), idx + 1]);
        }
    }
    return Number(maxSum - loss);
};

class Solution {
    public long kSum(int[] nums, int k) {
        long maxSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) maxSum += nums[i];
            else nums[i] = -nums[i];
        }
        Arrays.sort(nums);
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0L, 0L});
        long loss = 0;
        for (int i = 0; i < k - 1; i++) {
            long[] top = pq.poll();
            loss = top[0];
            int idx = (int) top[1];
            if (idx < nums.length) {
                pq.offer(new long[]{top[0] + nums[idx], idx + 1});
                if (idx > 0) {
                    pq.offer(new long[]{top[0] + nums[idx] - nums[idx - 1], idx + 1});
                }
            }
        }
        return maxSum - loss;
    }
}

class MinHeap {
    private h: [bigint, number][] = [];
    size(): number { return this.h.length; }
    push(v: [bigint, number]): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): [bigint, number] {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function kSum(nums: number[], k: number): number {
    let maxSum = 0n;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) maxSum += BigInt(nums[i]);
        else nums[i] = -nums[i];
    }
    nums.sort((a, b) => a - b);
    const pq = new MinHeap();
    pq.push([0n, 0]);
    let loss = 0n;
    for (let i = 0; i < k - 1; i++) {
        const [l, idx] = pq.pop();
        loss = l;
        if (idx < nums.length) {
            pq.push([l + BigInt(nums[idx]), idx + 1]);
            if (idx > 0) pq.push([l + BigInt(nums[idx]) - BigInt(nums[idx - 1]), idx + 1]);
        }
    }
    return Number(maxSum - loss);
}