aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-28 12:11:05 -0600
committerJack Sangdahl <[email protected]>2024-09-28 12:11:05 -0600
commitd07bde235619e5052d9a5de8a0337216290b0bd4 (patch)
tree624a1ce72e921180972d1f1794bf48ce150771fc
parent4d605daa0713126555d61b26af7635cff249a160 (diff)
downloadleetcode-d07bde235619e5052d9a5de8a0337216290b0bd4.tar.gz
leetcode-d07bde235619e5052d9a5de8a0337216290b0bd4.zip
2461. maximum sum of distinct subarrays with length k
-rw-r--r--max_sum_distinct_subarr.c66
-rw-r--r--max_sum_distinct_subarr.py35
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))