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 – DP with Last Seen Parity

Intuition

To meet the condition, a valid subsequence can be formed by:

  • Using only even numbers.
  • Using only odd numbers.
  • Alternating between even and odd, so every odd is followed by even and vice versa. We track the best result for each case and maximize over all.

Approach

  1. Track the longest subsequence ending at each position, and the last seen even and odd positions.
  2. For each number, update the DP for both the alternating and single-parity cases.
  3. The answer is the maximum among the DP, even count, and odd count.

Code

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

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1, 0);
        int lastEven = 0, lastOdd = 0, evenCount = 0, oddCount = 0;
        for (int i = 1; i <= n; ++i) {
            if (nums[i-1] % 2 == 0) {
                dp[i] = max(dp[i-1], dp[lastOdd] + 1);
                lastEven = i;
                ++evenCount;
            } else {
                dp[i] = max(dp[i-1], dp[lastEven] + 1);
                lastOdd = i;
                ++oddCount;
            }
        }
        return max({dp[n], evenCount, oddCount});
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func maximumLength(nums []int) int {
    n := len(nums)
    dp := make([]int, n+1)
    lastEven, lastOdd := 0, 0
    evenCount, oddCount := 0, 0
    for i := 1; i <= n; i++ {
        if nums[i-1]%2 == 0 {
            dp[i] = max(dp[i-1], dp[lastOdd]+1)
            lastEven = i
            evenCount++
        } else {
            dp[i] = max(dp[i-1], dp[lastEven]+1)
            lastOdd = i
            oddCount++
        }
    }
    return max3(dp[n], evenCount, oddCount)
}
func max(a, b int) int { if a > b { return a }; return b }
func max3(a, b, c int) int { return max(a, max(b, c)) }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maximumLength(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        int lastEven = 0, lastOdd = 0, evenCount = 0, oddCount = 0;
        for (int i = 1; i <= n; ++i) {
            if (nums[i-1] % 2 == 0) {
                dp[i] = Math.max(dp[i-1], dp[lastOdd] + 1);
                lastEven = i;
                evenCount++;
            } else {
                dp[i] = Math.max(dp[i-1], dp[lastEven] + 1);
                lastOdd = i;
                oddCount++;
            }
        }
        return Math.max(dp[n], Math.max(evenCount, oddCount));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun maximumLength(nums: IntArray): Int {
        val dp = IntArray(nums.size + 1) { 0 }
        var lastEven = 0
        var lastOdd = 0
        var evenCount = 0
        var oddCount = 0
        for (i in 1..nums.size) {
            if (nums[i - 1] % 2 == 0) {
                dp[i] = maxOf(dp[i - 1], dp[lastOdd] + 1)
                lastEven = i
                evenCount++
            } else {
                dp[i] = maxOf(dp[i - 1], dp[lastEven] + 1)
                lastOdd = i
                oddCount++
            }
        }
        return maxOf(dp[nums.size], evenCount, oddCount)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from typing import List
class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n+1)
        last_even = 0
        last_odd = 0
        even_count = 0
        odd_count = 0
        for i in range(1, n+1):
            if nums[i-1] % 2 == 0:
                dp[i] = max(dp[i-1], dp[last_odd] + 1)
                last_even = i
                even_count += 1
            else:
                dp[i] = max(dp[i-1], dp[last_even] + 1)
                last_odd = i
                odd_count += 1
        return max(dp[n], even_count, odd_count)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn maximum_length(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![0; n+1];
        let (mut last_even, mut last_odd) = (0, 0);
        let (mut even_count, mut odd_count) = (0, 0);
        for i in 1..=n {
            if nums[i-1] % 2 == 0 {
                dp[i] = dp[i-1].max(dp[last_odd] + 1);
                last_even = i;
                even_count += 1;
            } else {
                dp[i] = dp[i-1].max(dp[last_even] + 1);
                last_odd = i;
                odd_count += 1;
            }
        }
        *[dp[n], even_count, odd_count].iter().max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maximumLength(nums: number[]): number {
        const n = nums.length;
        const dp = Array(n+1).fill(0);
        let lastEven = 0, lastOdd = 0, evenCount = 0, oddCount = 0;
        for (let i = 1; i <= n; ++i) {
            if (nums[i-1] % 2 === 0) {
                dp[i] = Math.max(dp[i-1], dp[lastOdd] + 1);
                lastEven = i;
                evenCount++;
            } else {
                dp[i] = Math.max(dp[i-1], dp[lastEven] + 1);
                lastOdd = i;
                oddCount++;
            }
        }
        return Math.max(dp[n], evenCount, oddCount);
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is processed once.
  • 🧺 Space complexity: O(n), for the DP array.