🔗 🟡 3202. Find the Maximum Length of Valid Subsequence II

tags: `陣列(Array)` `動態規劃(Dynamic Programming)`

題意

給定一個整數陣列 $nums$ 和一個正整數 $k$ 。

如果 $nums$ 的一個長度為 $x$ 的子序列(Subsequence) $sub$ 滿足以下條件，則稱其為有效的：

$(sub[0] + sub[1]) \mod k == (sub[1] + sub[2]) \mod k == \cdots == (sub[x - 2] + sub[x - 1]) \mod k$

返回 $nums$ 中最長的有效子序列的長度。

約束條件

$2 \leq \text{nums.length} \leq 10^3$
$1 \leq \text{nums[i]} \leq 10^7$
$1 \leq k \leq 10^3$

思路：動態規劃(Dynamic Programming)

首先，我們觀察到條件 $(a + b) \pmod k = s$ 只跟 $a \pmod k$ 和 $b \pmod k$ 有關，而與 $a$ 和 $b$ 的原始數值無關。因此，我們可以先對 $nums$ 陣列中的所有數字進行預處理，將它們全部轉換為模 $k$ 的餘數。這可以大大簡化後續的計算。

方法一：枚舉子序列中相鄰兩項的和 $s$

這道題要求我們找出一個最長的子序列，使得子序列中任意相鄰兩項的和，在模 $k$ 意義下都是一個定值。

由於這個定值是多少我們事先並不知道，一個直觀的想法是枚舉所有可能的定值。令這個定值為 $s$ ，其中 $s$ 的可能範圍是 $0, 1, \dots, k-1$ 。對於每一個固定的 $s$ ，求解滿足 (sub[i-1] + sub[i]) % k == s 的最長子序列長度。最後，取所有 $s$ 對應的最長長度中的最大值，即為本題的答案。

接下來的問題是，對於一個固定的 $s$ ，如何找出最長的有效子序列？這是一個典型的動態規劃(Dynamic Programming) 問題。我們可以定義一個大小為 $(n + 1) \times k$ 的 DP 陣列 $f$ ，其中 $f[i][j]$ 表示考慮前 $i$ 個數，任兩項和為 $s$ 時，最後一項模 $k$ 為 $j$ 時的最大長度。

當我們遍歷 nums 陣列中的每一個元素 x = nums[i] 時，可以透過選或不選 x 來更新 f：

如果我們要將 x 作為有效子序列的最新一項，那麼它的前一項 prev 必須滿足 $(prev + x) \pmod k = s$ 。
透過移項，我們可以得到 $prev \pmod k = (s - x) \pmod k$ ，也就是可以從 $f[(s - x) \bmod k]$ 轉移過來。
如果不選 x，則 $f[i][x] = f[i - 1][x]$ 。

得到狀態轉移方程：

$f[i][x] = \begin{cases} \max\left(f[i-1][x],\ f[i-1][(s-x)\bmod k] + 1\right), & \text{if } x = \mathrm{nums}[i] \bmod k \\ f[i-1][x], & \text{otherwise} \end{cases}$

由於從 $f[i - 1]$ 轉移到 $f[i]$ 時，只依賴於 $f[i - 1]$ 的狀態，可以用滾動陣列(Rolling Array) 的方式壓縮維度，又因為轉移時只需要多考慮最後一項為 x = nums[i] 的情況，因此除了 $f[i][x]$ 之外，其餘的值都和 $f[i - 1]$ 相同。

在這種寫法中，就算沒有注意到以下性質，直接對選或不選兩種情況取最大值也能通過。

值得注意的是，由於子序列中一定是 $x, y, \cdots, x, y$ 交錯，因此在選或不選 $nums[i]$ 的兩種情況中，選一定不會比不選差。這是因為如果在上一個 $y$ 之後、當前的 $x$ 之前，有出現其他的 $x^{\prime}$ ，則此時 $f[x]$ 的值已經且最多是 $f[y] + 1$ ；如果沒有，則選當前的 $x$ 一定能得到更優的結果，可以用反證法證明。因此選 $x$ 一定不會比不選差。

複雜度分析

時間複雜度： $O(k \times (k + n))$
空間複雜度： $O(k)$

fmax = lambda x, y: x if x > y else y
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        nums[:] = [x % k for x in nums]
        ans = 0
        # 枚舉 (sub[0] + sub[1]) % k 的值
        for s in range(k):
            f = [0] * k
            for x in nums:
                # f[x] = fmax(f[x], f[(s - x) % k] + 1)  # 選或不選 nums[i]
                f[x] = f[(s - x) % k] + 1  # 但選了一定不會比不選差
            ans = fmax(ans, max(f))
        return ans

#include <ranges>
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        auto arr = nums | views::transform([k](int x) { return x % k; });
        int ans = 0;
        for (int s = 0; s < k; ++s) {
            vector<int> f(k, 0);
            for (int x : arr)
                f[x] = f[(s - x + k) % k] + 1;
            ans = max(ans, ranges::max(f));
        }
        return ans;
    }
};

方法二：紀錄最後兩項

由於省略了許多相似之處的說明，建議先觀看完方法一的說明再閱讀此方法。

首先，觀察到一個有效的子序列，其元素的餘數序列必定呈現 $y, x, y, x, \cdots$ 這樣的交錯模式。因此，只需要紀錄最後兩項的餘數即可。

令 $f[i][y][x]$ 表示考慮前 $i$ 個數，最後兩項的餘數為 $y, x$ 時的最大長度，則可以得到狀態轉移方程：

$f[i][y][x] = \begin{cases} \max\left(f[i-1][y][x],\ f[i-1][x][y] + 1\right), & \text{if } x = \mathrm{nums}[i] \bmod k \\ f[i-1][y][x], & \text{otherwise} \end{cases}$

同樣地，由於從 $f[i - 1]$ 轉移到 $f[i]$ 時，只依賴於 $f[i - 1]$ 的狀態，可以用滾動的方式壓縮維度，又因為轉移時只需要多考慮最後一項為 x = nums[i] 的情況，因此除了 $f[i][y][x]$ 之外，其餘的值都和 $f[i - 1]$ 相同。

類似地，在選或不選 $nums[i]$ 的兩種情況中，選一定不會比不選差。

複雜度分析

時間複雜度： $O(k^2 + n \cdot k)$
空間複雜度： $O(k^2)$

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        f = [[0] * k for _ in range(k)]
        for x in map(lambda x: x % k, nums):
            for y in range(k):
                f[y][x] = f[x][y] + 1
        return max(map(max, f))

#include <ranges>
class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        vector<vector<int>> f(k, vector<int>(k, 0));
        for (int x : nums | views::transform([k](int x) { return x % k; }))
            for (int y = 0; y < k; ++y)
                f[y][x] = f[x][y] + 1;
        return ranges::max(f | views::transform(ranges::max));
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, perfect hands, vibrant colors, anime style, cover art, illustration, depth of field, sharp focus, impactful picture, official art, (chocoan:0.5), (mika Pikazo:0.4), (artist: sheya:0.5), (wlop:0.4),

1girl, solo, Lillie, lillie (pokemon), green eyes, long hair, blonde hair, blunt bangs, twin braids, white sun hat, hat, white hat, white dress, sun hat, sleeveless dress, collared dress, contrast collar, round collar, standing outdoors, leaning casually against a wooden railing, wind blowing her hair and dress, expansive grassy field and ocean in the background, wind turbines in the distance, clear blue sky, bright sunlight, relaxed and breezy atmosphere,

Lillie stands gracefully by a wooden fence overlooking a vibrant green field and the sparkling ocean, with wind turbines spinning gently in the distance under a wide, clear blue sky. The sunlight dances across her white dress and sun hat as the breeze stirs her hair, creating a serene and refreshing coastal scene.