leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

find_max_len_valid_subseq1.c (1828B)

 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
// 3201. Find the Maximum Length of Valid Subsequence I
#include "leetcode.h"

/*
 * you are given an integer array 'nums'. a subsequence 'sub' of 'nums' with
 * length 'x' is called valid if it satisfies '(sub[0] + sub[1]) % 2 == (sub[1]
 * + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2'. return the legnth of
 * the longest valid subsequences of 'nums'. a subsequence is an array that can
 * be derived from another array by deleting some or no elements without
 * changing the order of the remaining elements.
 */

int maximumLength(int *nums, int numsSize) {
  int odd_start = 0, even_start = 0;
  for (int i = 0; i < numsSize; i++) {
    if (!(nums[odd_start] % 2) && (nums[i] % 2 == 1))
      odd_start = i;
    if ((nums[even_start] % 2 == 1) && !(nums[i] % 2))
      even_start = i;
  }
  int odd_cnt1 = 1, odd_i1 = odd_start, odd_cnt2 = 1, odd_i2 = even_start;
  int even_cnt1 = 1, even_i1 = odd_start, even_cnt2 = 1, even_i2 = even_start;
  for (int i = odd_start + 1; i < numsSize; i++) {
    if ((nums[odd_i1] + nums[i]) % 2 == 1) {
      odd_i1 = i;
      odd_cnt1++;
    }
    if (!((nums[even_i1] + nums[i]) % 2)) {
      even_i1 = i;
      even_cnt1++;
    }
  }
  for (int i = even_start + 1; i < numsSize; i++) {
    if ((nums[odd_i2] + nums[i]) % 2 == 1) {
      odd_i2 = i;
      odd_cnt2++;
    }
    if (!((nums[even_i2] + nums[i]) % 2)) {
      even_i2 = i;
      even_cnt2++;
    }
  }
  int odd_max = fmax(odd_cnt1, odd_cnt2);
  int even_max = fmaxl(even_cnt1, even_cnt2);
  return fmax(odd_max, even_max);
}

int main() {
  int n1[] = {1, 2, 3, 4}, n2[] = {1, 2, 1, 1, 2, 1, 2}, n3[] = {1, 3};
  printf("%d\n", maximumLength(n1, ARRAY_SIZE(n1))); // expect: 4
  printf("%d\n", maximumLength(n2, ARRAY_SIZE(n2))); // expect: 6
  printf("%d\n", maximumLength(n3, ARRAY_SIZE(n3))); // expect: 2
}