寻找最长非递减偶数或奇数子序列

寻找最长非递减偶数或奇数子序列

给定一个正整数序列，找出其中最长的非递减子序列，该子序列要求要么是所有元素都是偶数，要么是所有元素都是奇数。

算法思路：

假设给定的正整数序列为nums，可以采用动态规划的方式解决。

定义两个数组even和odd，其中even[i]表示以nums[i]为结尾的最长非递减偶数子序列长度，odd[i]表示以nums[i]为结尾的最长非递减奇数子序列长度。

初始化even和odd数组的所有元素为1，因为每个数都可以看作长度为1的子序列。

然后从第二个数开始遍历nums数组，对于每个数nums[i]，分别与前面的数比较，如果前面的数nums[j]小于等于nums[i]，则可以将nums[i]接在nums[j]后面形成一个更长的非递减序列，此时需要判断nums[j]和nums[i]的奇偶性。

• 如果nums[i]和nums[j]都是偶数，则可以将nums[i]接在nums[j]后面形成一个更长的偶数序列，此时even[i]的值可以更新为even[j]+1；
• 如果nums[i]和nums[j]都是奇数，则可以将nums[i]接在nums[j]后面形成一个更长的奇数序列，此时odd[i]的值可以更新为odd[j]+1；
• 如果nums[i]是偶数，nums[j]是奇数，则不能将nums[i]接在nums[j]后面形成一个非递减序列，需要跳过。

最后找到even和odd数组中的最大值，即为所求的最长子序列长度。

Python代码实现：

def find_longest_subsequence(nums):
    n = len(nums)
    even = [1] * n
    odd = [1] * n
    res = 1
    for i in range(1, n):
        for j in range(i):
            if nums[j] <= nums[i]:
                if nums[i] % 2 == 0 and nums[j] % 2 == 0:
                    even[i] = max(even[i], even[j] + 1)
                elif nums[i] % 2 == 1 and nums[j] % 2 == 1:
                    odd[i] = max(odd[i], odd[j] + 1)
        res = max(res, even[i], odd[i])
    return res

时间复杂度： O(n^2)

空间复杂度： O(n)