aboutsummaryrefslogtreecommitdiff
path: root/find_subseq_len_k_large_sum.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_subseq_len_k_large_sum.c')
-rw-r--r--find_subseq_len_k_large_sum.c62
1 files changed, 62 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);
+}