aboutsummaryrefslogtreecommitdiff
path: root/longest_harmonious_subseq.c
diff options
context:
space:
mode:
Diffstat (limited to 'longest_harmonious_subseq.c')
-rw-r--r--longest_harmonious_subseq.c62
1 files changed, 62 insertions, 0 deletions
diff --git a/longest_harmonious_subseq.c b/longest_harmonious_subseq.c
new file mode 100644
index 0000000..1c1e5b4
--- /dev/null
+++ b/longest_harmonious_subseq.c
@@ -0,0 +1,62 @@
+// 594. Longest Harmonious Subsequence
+#include "leetcode.h"
+
+/*
+ * we define a harmonious array as an array where the difference between its
+ * maximum value and its minimum value is exactly 1. given an integer array
+ * 'nums', return the length of the its longest harmonious subsequnce among all
+ * its possible subsequnces.
+ */
+
+struct hash {
+ int num;
+ int cnt;
+ UT_hash_handle hh;
+};
+
+struct hash *mem;
+static int idx;
+
+int *entry(struct hash **set, int n) {
+ struct hash *tmp;
+ HASH_FIND_INT(*set, &n, tmp);
+ if (!tmp) {
+ tmp = &mem[idx++];
+ tmp->num = n;
+ tmp->cnt = 0;
+ HASH_ADD_INT(*set, num, tmp);
+ }
+ return &(tmp->cnt);
+}
+
+bool contains(struct hash **obj, int num) {
+ struct hash *tmp;
+ HASH_FIND_INT(*obj, &num, tmp);
+ return tmp;
+}
+
+int findLHS(int *nums, int numsSize) {
+ struct hash *set = NULL, *p, *tmp, *s;
+ int ans = 0;
+ idx = 0;
+ mem = (struct hash *)calloc(numsSize, sizeof(struct hash));
+ for (int i = 0; i < numsSize; i++)
+ (*entry(&set, nums[i]))++;
+ HASH_ITER(hh, set, s, tmp) {
+ int key = s->num;
+ if (contains(&set, key + 1)) {
+ int sum = *entry(&set, key) + *entry(&set, key + 1);
+ if (sum > ans)
+ ans = sum;
+ }
+ }
+ free(mem);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 3, 2, 2, 5, 2, 3, 7}, n2[] = {1, 2, 3, 4}, n3[] = {1, 1, 1, 1};
+ printf("%d\n", findLHS(n1, ARRAY_SIZE(n1))); // expect: 5
+ printf("%d\n", findLHS(n2, ARRAY_SIZE(n2))); // expect: 2
+ printf("%d\n", findLHS(n3, ARRAY_SIZE(n3))); // expect: 0
+}