Welcome to Subscribe On Youtube

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 $\text{nums}$, and $k=2$.

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • 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
    }
    
  • 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;
    }
    
    

All Problems

All Solutions