diff options
author | Jack Sangdahl <[email protected]> | 2024-09-28 12:11:05 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-28 12:11:05 -0600 |
commit | d07bde235619e5052d9a5de8a0337216290b0bd4 (patch) | |
tree | 624a1ce72e921180972d1f1794bf48ce150771fc | |
parent | 4d605daa0713126555d61b26af7635cff249a160 (diff) | |
download | leetcode-d07bde235619e5052d9a5de8a0337216290b0bd4.tar.gz leetcode-d07bde235619e5052d9a5de8a0337216290b0bd4.zip |
2461. maximum sum of distinct subarrays with length k
-rw-r--r-- | max_sum_distinct_subarr.c | 66 | ||||
-rw-r--r-- | max_sum_distinct_subarr.py | 35 |
2 files changed, 101 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 +} diff --git a/max_sum_distinct_subarr.py b/max_sum_distinct_subarr.py new file mode 100644 index 0000000..28f3a84 --- /dev/null +++ b/max_sum_distinct_subarr.py @@ -0,0 +1,35 @@ +# 2461. Maximum Sum of Distinct Subarrays With Length K + +""" +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 +""" + + +class Solution(object): + def maximumSubarraySum(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ans, curr, pos, dup = 0, 0, [-1] * 100001, -1 + for i in range(0, len(nums)): + curr += nums[i] + if i >= k: + curr -= nums[i - k] + dup = max(dup, pos[nums[i]]) + if i - dup >= k: + ans = max(ans, curr) + pos[nums[i]] = i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumSubarraySum(nums=[1, 5, 4, 2, 9, 9, 9], k=3)) + print(obj.maximumSubarraySum(nums=[4, 4, 4], k=3)) |