在Python中查找给定列表中最长交替子序列的长度

交替子序列是指一个序列中相邻的元素交替出现。例如，[1, 2, 1, 2, 1, 2] 就是一个交替子序列。给定一个列表，需要找出其最长的交替子序列，并返回其长度。

解决方法

方法一：动态规划

首先我们可以利用动态规划来解决这个问题。设 dp[i][0] 和 dp[i][1] 分别表示以第 i 个元素结尾的，且当前元素为偶数和奇数的最长交替子序列长度。则我们可以得到以下转移方程：

if nums[i] % 2 == 0: # 如果当前元素为偶数
    dp[i][0] = dp[j][1] + 1 
else: # 如果当前元素为奇数
    dp[i][1] = dp[j][0] + 1

其中 j 表示满足 nums[j]!=nums[i] 且 j<i 的最大值。

最终，我们只需要返回 dp 中的最大值。

示例代码如下：

def alternatingsubsequence(nums: List[int]) -> int:
    n = len(nums)
    dp = [[1,1] for i in range(n)]
    res = 1
    for i in range(1,n):
        for j in range(i):
            if nums[i] % 2 == 0: # 如果当前元素为偶数
                if nums[j] % 2 == 1 and nums[j] != nums[i]: # 如果之前的元素为奇数且两个元素不相同
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)
            else: # 如果当前元素为奇数
                if nums[j] % 2 == 0 and nums[j] != nums[i]: # 如果之前的元素为偶数且两个元素不相同
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)
        res = max(res, max(dp[i]))

    return res

方法二：双指针

我们还可以利用双指针来解决这个问题，设置两个指针 i 和 j，分别指向相邻的两个元素。如果当前的元素与上一个元素不同，那么我们就让当前的交替子序列长度加 1，然后更新最大长度。最后返回最大的交替子序列长度即可。

示例代码如下：

def alternatingsubsequence(nums: List[int]) -> int:
    n = len(nums)
    res, cur = 1, 1
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            cur += 1
            res = max(res, cur)
        else:
            cur = 1
    return res