3201. Find the Maximum Length of Valid Subsequence I LeetCode Solution
In this guide, you will get 3201. Find the Maximum Length of Valid Subsequence I LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Length of Valid Subsequence I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
3201. Find the Maximum Length of Valid Subsequence I LeetCode Solution in C++
class Solution {
public:
int maximumLength(vector<int>& nums) {
// dp[i][j] := the maximum length of a valid subsequence, where the last
// number mod 2 equal to i and the next desired number mod 2 equal to j
vector<vector<int>> dp(2, vector<int>(2));
// Extend the pattern xyxyxy...xy.
for (const int x : nums)
for (int y = 0; y < 2; ++y)
dp[x % 2][y] = dp[y][x % 2] + 1;
return accumulate(dp.begin(), dp.end(), 0,
[](int acc, const vector<int>& row) {
return max(acc, ranges::max(row));
});
}
}; /* code provided by PROGIEZ */
3201. Find the Maximum Length of Valid Subsequence I LeetCode Solution in Java
class Solution {
public int maximumLength(int[] nums) {
// dp[i][j] := the maximum length of a valid subsequence, where the last
// number mod 2 equal to i and the next desired number mod 2 equal to j
int[][] dp = new int[k][k];
// Extend the pattern xyxyxy...xy.
for (final int x : nums)
for (int y = 0; y < 2; ++y)
dp[x % 2][y] = dp[y][x % 2] + 1;
return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
}
} // code provided by PROGIEZ
3201. Find the Maximum Length of Valid Subsequence I LeetCode Solution in Python
class Solution:
def maximumLength(self, nums: list[int]) -> int:
# dp[i][j] := the maximum length of a valid subsequence, where the last
# number mod k equal to i and the next desired number mod k equal to j
dp = [[0] * 2 for _ in range(2)]
# Extend the pattern xyxyxy...xy.
for x in nums:
for y in range(2):
dp[x % 2][y] = dp[y][x % 2] + 1
return max(map(max, dp)) # code by PROGIEZ
