aboutsummaryrefslogtreecommitdiff
path: root/find_subseq_len_k_large_sum.c
blob: ad29aa5c149c8189bf349f5166e9a1e1c5e2a7bc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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);
}