diff options
Diffstat (limited to 'find_max_len_valid_subseq2.c')
-rw-r--r-- | find_max_len_valid_subseq2.c | 68 |
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 +} |