Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8


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

Output: 4

Explanation:

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

Example 2

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7
8


Input: nums = [1,3]

Output: 2

Explanation:

The longest valid subsequence is `[1, 3]`.

Constraints

  • 2 <= nums.length <= 2 * 10^5
  • 1 <= nums[i] <= 10^7

Solution

Method 1 – Dynamic Programming by Parity

Intuition

A valid subsequence requires that the parity (even/odd) of the sum of every two consecutive elements is the same throughout. This means, for any valid subsequence, the parity of sub[i] + sub[i+1] is constant. We can use dynamic programming to track the longest subsequence for each possible parity.

Approach

  1. For each number, try to extend the longest subsequence ending with each possible parity (0 or 1).
  2. Use a DP array where dp[p] is the length of the longest subsequence ending with parity p.
  3. For each number, update the DP for both parities by considering all previous parities.
  4. The answer is the maximum value in the DP array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int longestValidSubsequence(vector<int>& nums) {
        int n = nums.size(), ans = 1;
        vector<int> dp(2, 0);
        for(int x : nums) {
            vector<int> ndp = dp;
            for(int p=0;p<2;++p) {
                int cur = 1;
                if(dp[p]) {
                    int parity = (p + x) % 2;
                    cur = dp[p] + 1;
                    ndp[parity] = max(ndp[parity], cur);
                }
                ndp[x%2] = max(ndp[x%2], 1);
            }
            dp = ndp;
            ans = max(ans, max(dp[0], dp[1]));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func longestValidSubsequence(nums []int) int {
    dp := [2]int{}
    ans := 1
    for _, x := range nums {
        ndp := dp
        for p := 0; p < 2; p++ {
            cur := 1
            if dp[p] > 0 {
                parity := (p + x) % 2
                cur = dp[p] + 1
                if ndp[parity] < cur {
                    ndp[parity] = cur
                }
            }
            if ndp[x%2] < 1 {
                ndp[x%2] = 1
            }
        }
        dp = ndp
        if ans < dp[0] { ans = dp[0] }
        if ans < dp[1] { ans = dp[1] }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int longestValidSubsequence(int[] nums) {
        int[] dp = new int[2];
        int ans = 1;
        for(int x : nums) {
            int[] ndp = dp.clone();
            for(int p=0;p<2;++p) {
                int cur = 1;
                if(dp[p]>0) {
                    int parity = (p + x) % 2;
                    cur = dp[p] + 1;
                    ndp[parity] = Math.max(ndp[parity], cur);
                }
                ndp[x%2] = Math.max(ndp[x%2], 1);
            }
            dp = ndp;
            ans = Math.max(ans, Math.max(dp[0], dp[1]));
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun longestValidSubsequence(nums: IntArray): Int {
        var dp = IntArray(2)
        var ans = 1
        for (x in nums) {
            val ndp = dp.copyOf()
            for (p in 0..1) {
                var cur = 1
                if (dp[p] > 0) {
                    val parity = (p + x) % 2
                    cur = dp[p] + 1
                    ndp[parity] = maxOf(ndp[parity], cur)
                }
                ndp[x%2] = maxOf(ndp[x%2], 1)
            }
            dp = ndp
            ans = maxOf(ans, dp[0], dp[1])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def longestValidSubsequence(self, nums: list[int]) -> int:
        dp = [0, 0]
        ans = 1
        for x in nums:
            ndp = dp[:]
            for p in range(2):
                cur = 1
                if dp[p]:
                    parity = (p + x) % 2
                    cur = dp[p] + 1
                    ndp[parity] = max(ndp[parity], cur)
                ndp[x%2] = max(ndp[x%2], 1)
            dp = ndp
            ans = max(ans, dp[0], dp[1])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn longest_valid_subsequence(nums: Vec<i32>) -> i32 {
        let mut dp = [0, 0];
        let mut ans = 1;
        for &x in &nums {
            let mut ndp = dp;
            for p in 0..2 {
                let mut cur = 1;
                if dp[p] > 0 {
                    let parity = (p + x as usize) % 2;
                    cur = dp[p] + 1;
                    ndp[parity] = ndp[parity].max(cur);
                }
                ndp[(x%2) as usize] = ndp[(x%2) as usize].max(1);
            }
            dp = ndp;
            ans = ans.max(dp[0]).max(dp[1]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    longestValidSubsequence(nums: number[]): number {
        let dp = [0, 0];
        let ans = 1;
        for(const x of nums) {
            const ndp = dp.slice();
            for(let p=0;p<2;++p) {
                let cur = 1;
                if(dp[p]) {
                    const parity = (p + x) % 2;
                    cur = dp[p] + 1;
                    ndp[parity] = Math.max(ndp[parity], cur);
                }
                ndp[x%2] = Math.max(ndp[x%2], 1);
            }
            dp = ndp;
            ans = Math.max(ans, dp[0], dp[1]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.