diff options
author | Jack Sangdahl <[email protected]> | 2025-06-27 20:26:15 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-27 20:26:15 -0600 |
commit | eb7cdeeb68883d835f8b06e497f7b0d0a63ad05d (patch) | |
tree | b8ccbaae6da807b1d623f62d46e892736e977940 | |
parent | a96b65cbfad7f62f3db6b2eab105e4e25c0414c5 (diff) | |
download | leetcode-eb7cdeeb68883d835f8b06e497f7b0d0a63ad05d.tar.gz leetcode-eb7cdeeb68883d835f8b06e497f7b0d0a63ad05d.zip |
2099. find subsequence of length k with the largest sum
-rw-r--r-- | find_subseq_len_k_large_sum.c | 62 | ||||
-rw-r--r-- | find_subseq_len_k_large_sum.py | 32 |
2 files changed, 94 insertions, 0 deletions
diff --git a/find_subseq_len_k_large_sum.c b/find_subseq_len_k_large_sum.c new file mode 100644 index 0000000..ad29aa5 --- /dev/null +++ b/find_subseq_len_k_large_sum.c @@ -0,0 +1,62 @@ +// 2099. Find Subsequence of Length K With the Largest Sum +#include "leetcode.h" + +/* + * you are given an integer array 'nums' and an integer 'k'. you want to find a + * subsequence of 'nums' of length 'k' that has the largest sum. return any such + * subsequence as an integer array of length 'k'. a subsequence is an array that + * can be derived from another array by deleting some or no elements without + * changing the order of the remaining elements. + */ + +struct pair { + int idx; + int val; +}; + +int cmp_idx(const void *a, const void *b) { + struct pair aa = *(const struct pair *)a; + struct pair bb = *(const struct pair *)b; + return aa.idx - bb.idx; +} + +int cmp_val(const void *a, const void *b) { + struct pair aa = *(const struct pair *)a; + struct pair bb = *(const struct pair *)b; + return aa.val - bb.val; +} + +int *maxSubsequence(int *nums, int numsSize, int k, int *returnSize) { + struct pair *pairs = (struct pair *)malloc(numsSize * sizeof(struct pair)); + for (int i = 0; i < numsSize; i++) { + pairs[i].idx = i; + pairs[i].val = nums[i]; + } + qsort(pairs, numsSize, sizeof(struct pair), cmp_val); + qsort(pairs, k, sizeof(struct pair), cmp_idx); + int *ans = (int *)malloc(k * sizeof(int)); + *returnSize = k; + for (int i = 0; i < k; i++) + ans[i] = nums[pairs[i].idx]; + free(pairs); + return ans; +} + +int main() { + int n1[] = {2, 1, 3, 3}, n2[] = {-1, -2, 3, 4}, n3[] = {3, 4, 3, 3}; + int rs1, *ms1 = maxSubsequence(n1, ARRAY_SIZE(n1), 2, &rs1); + int rs2, *ms2 = maxSubsequence(n2, ARRAY_SIZE(n2), 3, &rs2); + int rs3, *ms3 = maxSubsequence(n3, ARRAY_SIZE(n3), 2, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", ms1[i]); // expect: 3 3 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", ms2[i]); // expect: -1 3 4 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", ms3[i]); // expect: 3 4 + printf("\n"); + free(ms1); + free(ms2); + free(ms3); +} diff --git a/find_subseq_len_k_large_sum.py b/find_subseq_len_k_large_sum.py new file mode 100644 index 0000000..c7ce933 --- /dev/null +++ b/find_subseq_len_k_large_sum.py @@ -0,0 +1,32 @@ +# 2099. Find Subsequence of Length K With the Largest Sum +import heapq + +""" +you are given an integer array 'nums' and an integer 'k'. you want to find a +subsequence of 'nums' of length 'k' that has the largest sum. return any such +subsequence as an integer array of length 'k'. a subsequence is an array that +can be derived from another array by deleting some or no elements without +changing the order of the remaining elements. +""" + + +class Solution(object): + def maxSubsequence(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: List[int] + """ + heap = [] + for i, j in enumerate(nums): + heapq.heappush(heap, (j, i)) + if len(heap) > k: + heapq.heappop(heap) + return [i[0] for i in sorted(heap, key=lambda x: x[1])] + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxSubsequence(nums=[2, 1, 3, 3], k=2)) + print(obj.maxSubsequence(nums=[-1, -2, 3, 4], k=3)) + print(obj.maxSubsequence(nums=[3, 4, 3, 3], k=2)) |