aboutsummaryrefslogtreecommitdiff
path: root/find_max_len_valid_subseq2.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_max_len_valid_subseq2.c')
-rw-r--r--find_max_len_valid_subseq2.c68
1 files changed, 68 insertions, 0 deletions
diff --git a/find_max_len_valid_subseq2.c b/find_max_len_valid_subseq2.c
new file mode 100644
index 0000000..3e60991
--- /dev/null
+++ b/find_max_len_valid_subseq2.c
@@ -0,0 +1,68 @@
+// 3202. Find the Maximum Length of Valid Subsequence II
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and a positive integer 'k'. a
+ * subsequence 'sub' of 'nums' with length 'x' is called valid if it satisfies
+ * '(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x
+ * - 1]) % k'. return the length of the longest valid subsequence of 'nums'
+ */
+
+int maximumLength(int *nums, int numsSize, int k) {
+ int *right = (int *)malloc(numsSize * sizeof(int));
+ for (int i = 0; i < numsSize; ++i)
+ right[i] = nums[i] % k;
+ int **left = (int **)malloc(k * sizeof(int *));
+ int *sizes = (int *)calloc(k, sizeof(int));
+ for (int i = 0; i < k; ++i)
+ left[i] = (int *)malloc(numsSize * sizeof(int));
+ for (int i = 0; i < numsSize; ++i) {
+ int rem = right[i];
+ left[rem][sizes[rem]++] = i;
+ }
+ int max = 0;
+ for (int i = 0; i < k; ++i)
+ if (sizes[i] > max)
+ max = sizes[i];
+ if (!k || k == 1) {
+ for (int i = 0; i < k; ++i)
+ free(left[i]);
+ free(left), free(right), free(sizes);
+ return max;
+ }
+ for (int x = 0; x < k; ++x)
+ for (int y = x + 1; y < k; ++y) {
+ int *a = left[x], la = sizes[x];
+ int *b = left[y], lb = sizes[y];
+ if (!la && !lb)
+ continue;
+ int i = 0, j = 0;
+ int sx = 0, sy = 0;
+ while (i < la || j < lb) {
+ if (j == lb || (i < la && a[i] < b[j])) {
+ int nx = sy > 0 ? sy + 1 : 1;
+ if (nx > sx)
+ sx = nx;
+ ++i;
+ } else {
+ int ny = sx > 0 ? sx + 1 : 1;
+ if (ny > sy)
+ sy = ny;
+ ++j;
+ }
+ }
+ int curr = sx > sy ? sx : sy;
+ if (curr > max)
+ max = curr;
+ }
+ for (int i = 0; i < k; ++i)
+ free(left[i]);
+ free(left), free(right), free(sizes);
+ return max;
+}
+
+int main() {
+ int n1[] = {1, 2, 3, 4, 5}, n2[] = {1, 4, 2, 3, 1, 4};
+ printf("%d\n", maximumLength(n1, ARRAY_SIZE(n1), 2)); // expect: 5
+ printf("%d\n", maximumLength(n2, ARRAY_SIZE(n2), 3)); // expect: 4
+}