aboutsummaryrefslogtreecommitdiff
path: root/max_sum_distinct_subarr.c
diff options
context:
space:
mode:
Diffstat (limited to 'max_sum_distinct_subarr.c')
-rw-r--r--max_sum_distinct_subarr.c66
1 files changed, 66 insertions, 0 deletions
diff --git a/max_sum_distinct_subarr.c b/max_sum_distinct_subarr.c
new file mode 100644
index 0000000..1efd979
--- /dev/null
+++ b/max_sum_distinct_subarr.c
@@ -0,0 +1,66 @@
+// 2461. Maximum Sum of Distinct Subarrays With Length K
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'k'. find the maximum
+ * subarray sum of all the subarrays of 'nums' that meet the following
+ * conditions. the length of the subarray is 'k' and all the elements of the
+ * subarray are distinct. return the maximum subarray of all the subarrays that
+ * meet the conditions. if no subarray meets the conditions, return 0. a
+ * subarray is a contiguous non empty sequence of elements within an array
+ */
+
+typedef struct {
+ UT_hash_handle hh;
+ int num;
+ int cnt;
+} hElem;
+
+long long maximumSubarraySum(int *nums, int numsSize, int k) {
+ hElem *map = NULL, *s, *t;
+ long long ans = 0, curr = 0;
+ int i = 0;
+ while (i < k && i < numsSize) {
+ HASH_FIND_INT(map, &nums[i], t);
+ if (!t) {
+ t = calloc(sizeof(hElem), 1);
+ t->num = nums[i];
+ HASH_ADD_INT(map, num, t);
+ }
+ t->cnt++;
+ curr += nums[i];
+ i++;
+ }
+ if (HASH_COUNT(map) == k)
+ ans = curr;
+ while (i < numsSize) {
+ HASH_FIND_INT(map, &nums[i], t);
+ if (!t) {
+ t = calloc(sizeof(hElem), 1);
+ t->num = nums[i];
+ HASH_ADD_INT(map, num, t);
+ }
+ t->cnt++;
+ int diff = nums[i - k];
+ HASH_FIND_INT(map, &diff, s);
+ if (s) {
+ s->cnt--;
+ if (!s->cnt) {
+ HASH_DEL(map, s);
+ free(s);
+ }
+ }
+ curr += nums[i];
+ curr -= nums[i - k];
+ if (HASH_COUNT(map) == k)
+ ans = fmax(ans, curr);
+ i++;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 5, 4, 2, 9, 9, 9}, n2[] = {4, 4, 4};
+ printf("%lld\n", maximumSubarraySum(n1, ARRAY_SIZE(n1), 3)); // expect: 15
+ printf("%lld\n", maximumSubarraySum(n2, ARRAY_SIZE(n2), 3)); // expect: 0
+}