Skip to content

3201. Find the Maximum Length of Valid Subsequence I

Description

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 length of the longest valid subsequence 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.

 

Example 1:

Input: nums = [1,2,3,4]

Output: 4

Explanation:

The longest valid subsequence is [1, 2, 3, 4].

Example 2:

Input: nums = [1,2,1,1,2,1,2]

Output: 6

Explanation:

The longest valid subsequence is [1, 2, 1, 2, 1, 2].

Example 3:

Input: nums = [1,3]

Output: 2

Explanation:

The longest valid subsequence is [1, 3].

 

Constraints:

  • 2 <= nums.length <= 2 * 105
  • 1 <= nums[i] <= 107

Solutions

Solution 1: Dynamic Programming

We set \(k = 2\).

Based on the problem description, we know that for a subsequence \(a_1, a_2, a_3, \cdots, a_x\), if it satisfies \((a_1 + a_2) \bmod k = (a_2 + a_3) \bmod k\). Then \(a_1 \bmod k = a_3 \bmod k\). This means that the result of taking modulo \(k\) for all odd-indexed elements is the same, and the result for all even-indexed elements is the same as well.

We can solve this problem using dynamic programming. Define the state \(f[x][y]\) as the length of the longest valid subsequence where the last element modulo \(k\) equals \(x\), and the second to last element modulo \(k\) equals \(y\). Initially, \(f[x][y] = 0\).

Iterate through the array \(nums\), and for each number \(x\), we get \(x = x \bmod k\). Then, we can enumerate the sequences where two consecutive numbers modulo \(j\) yield the same result, where \(j \in [0, k)\). Thus, the previous number modulo \(k\) would be \(y = (j - x + k) \bmod k\). At this point, \(f[x][y] = f[y][x] + 1\).

The answer is the maximum value among all \(f[x][y]\).

The time complexity is \(O(n \times k)\), and the space complexity is \(O(k^2)\). Here, \(n\) is the length of the array \(\textit{nums}\), and \(k=2\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        k = 2
        f = [[0] * k for _ in range(k)]
        ans = 0
        for x in nums:
            x %= k
            for j in range(k):
                y = (j - x + k) % k
                f[x][y] = f[y][x] + 1
                ans = max(ans, f[x][y])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int maximumLength(int[] nums) {
        int k = 2;
        int[][] f = new int[k][k];
        int ans = 0;
        for (int x : nums) {
            x %= k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x][y] = f[y][x] + 1;
                ans = Math.max(ans, f[x][y]);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int k = 2;
        int f[k][k];
        memset(f, 0, sizeof(f));
        int ans = 0;
        for (int x : nums) {
            x %= k;
            for (int j = 0; j < k; ++j) {
                int y = (j - x + k) % k;
                f[x][y] = f[y][x] + 1;
                ans = max(ans, f[x][y]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maximumLength(nums []int) (ans int) {
    k := 2
    f := make([][]int, k)
    for i := range f {
        f[i] = make([]int, k)
    }
    for _, x := range nums {
        x %= k
        for j := 0; j < k; j++ {
            y := (j - x + k) % k
            f[x][y] = f[y][x] + 1
            ans = max(ans, f[x][y])
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maximumLength(nums: number[]): number {
    const k = 2;
    const f: number[][] = Array.from({ length: k }, () => Array(k).fill(0));
    let ans: number = 0;
    for (let x of nums) {
        x %= k;
        for (let j = 0; j < k; ++j) {
            const y = (j - x + k) % k;
            f[x][y] = f[y][x] + 1;
            ans = Math.max(ans, f[x][y]);
        }
    }
    return ans;
}

Comments