leetcode

commit d07bde235619e5052d9a5de8a0337216290b0bd4
parent 4d605daa0713126555d61b26af7635cff249a160
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sat, 28 Sep 2024 12:11:05 -0600

2461. maximum sum of distinct subarrays with length k

Diffstat:
A
max_sum_distinct_subarr.c
 | 
66
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
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
@@ -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
@@ -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))