Find the Maximum Length of Valid Subsequence I

medium dynamic programming parity subsequence

Problem

Given an integer array nums, a subsequence sub of length x is valid when every adjacent pair shares the same sum-parity: (sub[0]+sub[1]) % 2 == (sub[1]+sub[2]) % 2 == … == (sub[x-2]+sub[x-1]) % 2. Return the length of the longest valid subsequence.

Only parity matters. A valid subsequence is one of four shapes: all elements even, all odd, or strictly alternating even/odd. We try each shape and keep the longest.

Inputnums = [1, 2, 1, 1, 2, 1, 2]

Output6

The alternating subsequence [1, 2, 1, 2, 1, 2] has length 6 — every adjacent sum is odd.

nums (comma-separated)

def maximumLength(nums):
    best = 0
    # t = required parity of every adjacent sum (0 or 1)
    for t in range(2):
        cur = [0, 0]              # cur[r] = longest valid run ending in parity r
        for v in nums:
            r = v % 2             # parity of current element
            prev = (t - r) % 2    # parity the previous element must have
            cur[r] = cur[prev] + 1
        best = max(best, cur[0], cur[1])
    return best

function maximumLength(nums) {
  let best = 0;
  // t = required parity of every adjacent sum (0 or 1)
  for (let t = 0; t < 2; t++) {
    const cur = [0, 0];          // cur[r] = longest valid run ending in parity r
    for (const v of nums) {
      const r = v % 2;           // parity of current element
      const prev = (t - r + 2) % 2; // parity the previous element must have
      cur[r] = cur[prev] + 1;
    }
    best = Math.max(best, cur[0], cur[1]);
  }
  return best;
}

int maximumLength(int[] nums) {
    int best = 0;
    // t = required parity of every adjacent sum (0 or 1)
    for (int t = 0; t < 2; t++) {
        int[] cur = {0, 0};          // cur[r] = longest run ending in parity r
        for (int v : nums) {
            int r = v % 2;           // parity of current element
            int prev = (t - r + 2) % 2; // parity the previous element needs
            cur[r] = cur[prev] + 1;
        }
        best = Math.max(best, Math.max(cur[0], cur[1]));
    }
    return best;
}

int maximumLength(vector<int>& nums) {
    int best = 0;
    // t = required parity of every adjacent sum (0 or 1)
    for (int t = 0; t < 2; t++) {
        int cur[2] = {0, 0};         // cur[r] = longest run ending in parity r
        for (int v : nums) {
            int r = v % 2;           // parity of current element
            int prev = (t - r + 2) % 2; // parity the previous element needs
            cur[r] = cur[prev] + 1;
        }
        best = max(best, max(cur[0], cur[1]));
    }
    return best;
}

Explanation

The validity rule depends only on parity (odd/even), not the actual values. Since every adjacent sum must equal the same value t = (a+b) % 2, the whole subsequence is pinned to one of just two regimes.

If t = 0, adjacent elements have equal parity, so every element of the subsequence is the same parity — either all even or all odd. If t = 1, adjacent elements have opposite parity, so the subsequence strictly alternates even/odd. That is the four shapes from the hint, captured by two values of t.

For a fixed t we run a tiny DP. cur[r] holds the length of the longest valid subsequence (with this target parity) ending in an element of parity r. When we read an element of parity r, the previous element must have parity prev = (t - r) % 2 so that their sum has parity t. We extend the best run ending in prev: cur[r] = cur[prev] + 1.

Because we always read elements left to right and take the most recent best, greedily appending the earliest valid element never hurts — every later element of the right parity can still attach. After scanning, the answer for this t is max(cur[0], cur[1]); the overall answer is the max across t = 0 and t = 1.

Example: nums = [1, 2, 1, 1, 2, 1, 2]. For t = 1 (alternating) the DP weaves the odds and evens together and reaches length 6, the subsequence [1, 2, 1, 2, 1, 2].

Time: O(n) Space: O(1)