3201. 找出有效子序列的最大长度 I

发表于2024-07-01更新于2024-07-02字数统计1.7k阅读时长17分阅读次数

摘要
Title: 3201. 找出有效子序列的最大长度 I
Categories: dfs, 记忆化搜索

Powered by:NEFU AB-IN

Link

3201. 找出有效子序列的最大长度 I

  • 题意

给你一个整数数组 nums。

nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == … == (sub[x - 2] + sub[x - 1]) % 2
返回 nums 的 最长的有效子序列 的长度。

一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。

  • 思路

  1. 贪心：最长有效子序列有三种可能：

    • 全都是奇元素
    • 全都是偶元素
    • 奇偶元素交替
      代码注意：
    • odd := sum(x & 1 for x in nums), 是海象表达式，赋值的同时返回值
    • sum((x & 1) ^ (y & 1) for x, y in std.pairwise(nums)) 这句话非常的巧妙，首先获取每一对相邻的元素，然后 (x & 1) ^ (y & 1) 会比较 x 和 y 的奇偶性，算和是计算所有相邻元素对的奇偶性差异
      • 比如 2 1 3 3 4 6，生成 [(2, 1), (1, 3), (3, 3), (3, 4), (4, 6)]，其中只有 (2, 1), (3, 4) 是奇偶性差异的 pair
        • 当出现 (0, 1) 的时候，如果再出现一个 (0, 1)，期间一定会夹杂着一个 (1, 0) 对
      • 但显然这个是 (0, 1) (1, 0)，即使 1 和 3 不同，但是我们可以选择一个，那么序列就可以为 214 或者 234，长度为 2 + 1 = 3
      • 所以 1 + sum((x & 1) ^ (y & 1) for x, y in pairwise(nums)) 等价于 奇偶交替的最长子序列长度

  2. dfs + 记忆化搜索
    为了考虑所有可能的初始状态，代码调用 dfs 函数四次，分别对应四种不同的初始状态：

    dfs(0, 0, 1)：从索引 0 开始，初始奇偶性为偶数，需要的奇偶性变化为 奇
    dfs(0, 0, 0)：从索引 0 开始，初始奇偶性为偶数，需要的奇偶性变化为 偶
    dfs(0, 1, 0)：从索引 0 开始，初始奇偶性为奇数，需要的奇偶性变化为 偶
    dfs(0, 1, 1)：从索引 0 开始，初始奇偶性为奇数，需要的奇偶性变化为 奇

    其实也是上面一样的思路，只不过用的dfs
    lru_cache 类似 cache，可以实现记忆化搜索

  • 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
'''
Author: NEFU AB-IN
Date: 2024-06-30 10:30:18
FilePath: \LeetCode\CP404\b\b.py
LastEditTime: 2024-07-01 20:39:53
'''
# 3.8.19 import
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin, stdout
from typing import Any, Dict, Generic, List, TypeVar, Union

TYPE = TypeVar('TYPE')

# Data structure
class SA(Generic[TYPE]):
    def __init__(self, x: TYPE, y: TYPE):
        self.x = x
        self.y = y

    def __lt__(self, other: 'SA[TYPE]') -> bool:
        return self.x < other.x

    def __eq__(self, other: 'SA[TYPE]') -> bool:
        return self.x == other.x and self.y == other.y

    def __repr__(self) -> str:
        return f'SA(x={self.x}, y={self.y})'


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
def input(): return stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
def read(): return map(int, input().split())
def read_list(): return list(read())


# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)
    
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE):
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)
    @staticmethod
    def pairwise(iterable):
        """Return successive overlapping pairs taken from the input iterable."""
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)

# ————————————————————— Division line ——————————————————————


class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        return max(
            odd := sum(x & 1 for x in nums),
            len(nums) - odd,
            1 + sum((x & 1) ^ (y & 1) for x, y in std.pairwise(nums))
        )

    def maximumLength(self, nums: List[int]) -> int:
        @lru_cache(None)
        def dfs(index, expected_parity, original_parity):
            # 递归终止条件：如果索引达到数组末尾，返回0
            if index == len(nums):
                return 0

            # 当前元素奇偶性符合预期
            if nums[index] % 2 == expected_parity:
                # 将当前元素加入子序列，并继续递归下一个元素
                # 更新expected_parity为(original_parity - expected_parity) % 2
                return 1 + dfs(index + 1, (original_parity - expected_parity) % 2, original_parity)
            else:
                # 当前元素不符合预期，不加入子序列，继续递归下一个元素
                return dfs(index + 1, expected_parity, original_parity)

        # 考虑所有可能的初始状态
        return max(dfs(0, 0, 1), dfs(0, 0, 0), dfs(0, 1, 0), dfs(0, 1, 1))

  • 拓展

当2变为k时，可以用dp解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
'''
Author: NEFU AB-IN
Date: 2024-06-30 10:30:18
FilePath: \LeetCode\CP404\c\c.py
LastEditTime: 2024-07-01 22:18:53
'''
# 3.8.19 import
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin, stdout
from typing import Any, Dict, Generic, List, TypeVar, Union

TYPE = TypeVar('TYPE')

# Data structure
class SA(Generic[TYPE]):
    def __init__(self, x: TYPE, y: TYPE):
        self.x = x
        self.y = y

    def __lt__(self, other: 'SA[TYPE]') -> bool:
        return self.x < other.x

    def __eq__(self, other: 'SA[TYPE]') -> bool:
        return self.x == other.x and self.y == other.y

    def __repr__(self) -> str:
        return f'SA(x={self.x}, y={self.y})'


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
def input(): return stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
def read(): return map(int, input().split())
def read_list(): return list(read())


# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)
    
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE):
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)
    @staticmethod
    def pairwise(iterable):
        """Return successive overlapping pairs taken from the input iterable."""
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)

# ————————————————————— Division line ——————————————————————


class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = std.array2d(0, n, k + OFFSET)

        if n <= 2:
            return n

        for j in range(k):
            dp[0][j] = 1
        res = 0
        for i in range(n):
            for j in range(i):
                dp[i][(nums[i] + nums[j]) % k] = std.max(dp[i][(nums[i] + nums[j]) % k], dp[j][(nums[i] + nums[j]) % k] + 1)
            res = std.max(res, max(dp[i]))

        return res

使用搜索：谷歌必应百度