diff options
Diffstat (limited to 'max_sum_distinct_subarr.c')
-rw-r--r-- | max_sum_distinct_subarr.c | 66 |
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 +} |