aboutsummaryrefslogtreecommitdiff
path: root/find_max_len_valid_subseq2.c
blob: 3e60991cc41cac4dee8637be39cddddd1048cb4b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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
}