leetcode

// 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
}