力扣每日一題--2025.7.16

📚 力扣每日一題–2025.7.16

📚 3201. 找出有效子序列的最大長度 I（中等）

今天我們要解決的是力扣上的第 3201 題——找出有效子序列的最大長度 I。這道題雖然標記為中等難度，但只要掌握了正確的思路，就能輕松解決！

📝 題目描述

在這里插入圖片描述

🤔 思路分析

核心需求推導過程 📝

題目要求子序列中所有相鄰元素之和的奇偶性必須相同，即：

(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x-2] + sub[x-1]) % 2

這個條件可以從兩個角度理解：

數學本質：所有相鄰元素對的和具有相同的奇偶性
序列特性：子序列中的元素必須形成一種特定的奇偶性模式

通過進一步推理，我們可以得出兩種基本的有效序列模式：

模式一：全同奇偶性序列

當要求相鄰元素之和為偶數時，所有元素必須具有相同的奇偶性
證明：若 a+b 為偶數且 b+c 為偶數，則 a 和 b 奇偶性相同，b 和 c 奇偶性相同，因此 a 和 c 奇偶性相同，以此類推

模式二：交替奇偶性序列

當要求相鄰元素之和為奇數時，元素必須交替出現奇偶性
證明：若 a+b 為奇數且 b+c 為奇數，則 a 和 b 奇偶性不同，b 和 c 奇偶性不同，因此 a 和 c 奇偶性相同，形成交替模式

讓我們通過具體示例驗證這些模式：

全奇序列 [1,3,5,7]：所有相鄰和都為偶數 (4,8,12)，符合模式一
奇偶交替序列 [1,2,3,4]：所有相鄰和都為奇數 (3,5,7)，符合模式二
混合序列 [1,2,2,3]：相鄰和為 3(奇)、4(偶)、5(奇)，不符合任何模式

所以，有效子序列有兩種基本類型：

所有相鄰元素之和都為偶數
所有相鄰元素之和都為奇數

我們需要分別找出這兩種類型的最長子序列，然后取較大值作為答案。

📑 解法探討

方法一：暴力枚舉（理解問題本質）

最直觀的思路是枚舉所有可能的子序列，檢查它們是否有效，并記錄最長有效子序列的長度。

這個官方的測試用例可以通過，但是提交的時候會超時，我這邊只是給大家提供一個思路方法。

/*** 方法一：暴力枚舉法* 思路：枚舉所有可能的子序列起點和兩種類型的有效子序列，*       構建并檢查每個子序列的有效性，記錄最長有效子序列長度* 注意：此方法僅用于理解問題本質，實際提交可能會超時*/
public class Solution {/*** 找出最長有效子序列的長度* @param nums 輸入的整數數組* @return 最長有效子序列的長度*/public int maximumLength(int[] nums) {int n = nums.length;// 邊界情況處理：空數組或單元素數組，直接返回數組長度if (n <= 1) return n;// 最小有效子序列長度為1（單個元素本身就是有效子序列）int maxLen = 1;// 枚舉所有可能的子序列起點for (int i = 0; i < n; i++) {// 嘗試兩種類型的有效子序列// type=0: 相鄰元素之和為偶數// type=1: 相鄰元素之和為奇數for (int type = 0; type <= 1; type++) {int len = 1;          // 當前子序列長度，至少包含起點元素int last = nums[i];   // 記錄子序列最后一個元素// 從起點后一個元素開始構建子序列for (int j = i + 1; j < n; j++) {// 計算當前元素與子序列最后一個元素之和的奇偶性int sumMod = (last + nums[j]) % 2;// 如果符合當前類型要求，則加入子序列if (sumMod == type) {len++;last = nums[j]; // 更新子序列最后一個元素}}// 更新最長有效子序列長度maxLen = Math.max(maxLen, len);}}return maxLen;}
}

復雜度分析：

時間復雜度：O(n2)，其中 n 是數組長度
空間復雜度：O(1)，只使用了常數額外空間

方法二：貪心算法（最優解法）

通過觀察，我們可以發現兩種類型的有效子序列具有明顯的模式：

類型 0（相鄰元素之和為偶數）：所有元素必須具有相同的奇偶性
- 全是偶數，或全是奇數
- 最長長度 = max(偶數元素個數, 奇數元素個數)
類型 1（相鄰元素之和為奇數）：元素必須交替出現奇偶性
- 奇偶奇偶…或偶奇偶奇…
- 最長長度取決于兩種模式中較長的一個

基于這些觀察，我們可以設計出 O(n)時間復雜度的貪心算法：

/*** 方法二：貪心算法（最優解法）* 思路：通過分析有效子序列的兩種模式，分別計算其最大長度*       類型0（相鄰和為偶數）：所有元素奇偶性相同，取較多的那種奇偶性元素個數*       類型1（相鄰和為奇數）：元素奇偶性交替出現，計算兩種起始模式的最大長度* 時間復雜度：O(n)，空間復雜度：O(1)*/
public class Solution {/*** 找出最長有效子序列的長度* @param nums 輸入的整數數組* @return 最長有效子序列的長度*/public int maximumLength(int[] nums) {int n = nums.length;// 邊界情況處理：空數組或單元素數組，直接返回數組長度if (n <= 1) return n;// 統計數組中奇數和偶數的個數int oddCount = 0, evenCount = 0;for (int num : nums) {if (num % 2 == 0) evenCount++;else oddCount++;}// 類型0的最大長度：所有元素奇偶性相同，取較多的那種int type0Max = Math.max(oddCount, evenCount);// 如果只有一種奇偶性，無法形成類型1的子序列（需要交替出現）if (oddCount == 0 || evenCount == 0) {return type0Max;}// 計算類型1的兩種模式的最大長度// 模式1：以奇數開始的交替序列（奇-偶-奇-偶...）int type1Max1 = calculateAlternatingLength(nums, true);// 模式2：以偶數開始的交替序列（偶-奇-偶-奇...）int type1Max2 = calculateAlternatingLength(nums, false);// 取兩種模式中的較大值int type1Max = Math.max(type1Max1, type1Max2);// 返回兩種類型中的最大值return Math.max(type0Max, type1Max);}/*** 計算交替奇偶性序列的長度* @param nums 輸入的整數數組* @param startWithOdd 是否以奇數開始* @return 交替序列的長度*/private int calculateAlternatingLength(int[] nums, boolean startWithOdd) {int length = 0;               // 序列長度boolean expectedOdd = startWithOdd; // 期望的下一個元素的奇偶性// 遍歷數組，構建交替序列for (int num : nums) {boolean isOdd = num % 2 == 1; // 當前元素是否為奇數// 如果當前元素符合期望的奇偶性，則加入序列if (isOdd == expectedOdd) {length++;expectedOdd = !expectedOdd; // 切換期望的奇偶性}}return length;}
}

復雜度分析：

時間復雜度：O(n)，只需遍歷數組幾次
空間復雜度：O(1)，只使用了常數額外空間

方法三：動態規劃（更通用的解決方案）

這個也超時了，但是方法思路應該是這樣的，之后我再想辦法去優化一下。

我們也可以使用動態規劃來解決這個問題，定義兩個狀態：

dp0[i]：以第 i 個元素結尾，且相鄰元素之和為偶數的最長有效子序列長度
dp1[i]：以第 i 個元素結尾，且相鄰元素之和為奇數的最長有效子序列長度

/*** 方法三：動態規劃（更通用的解決方案）* 思路：定義兩個狀態數組，分別記錄以每個位置結尾的兩種類型子序列的最大長度*       dp[i][0]：以第i個元素結尾，相鄰和為偶數的最長子序列長度*       dp[i][1]：以第i個元素結尾，相鄰和為奇數的最長子序列長度* 時間復雜度：O(n2)，空間復雜度：O(n)*/
public class Solution {/*** 找出最長有效子序列的長度* @param nums 輸入的整數數組* @return 最長有效子序列的長度*/public int maximumLength(int[] nums) {int n = nums.length;// 邊界情況處理：空數組或單元素數組，直接返回數組長度if (n <= 1) return n;// 動態規劃數組定義：// dp[i][0]：以第i個元素結尾，且相鄰元素之和為偶數的最長有效子序列長度// dp[i][1]：以第i個元素結尾，且相鄰元素之和為奇數的最長有效子序列長度int[][] dp = new int[n][2];// 初始化：第一個元素本身就是長度為1的有效子序列dp[0][0] = 1; // 以第一個元素結尾的類型0子序列dp[0][1] = 1; // 以第一個元素結尾的類型1子序列int maxLen = 1; // 記錄最長有效子序列長度// 從第二個元素開始計算for (int i = 1; i < n; i++) {// 默認情況下，子序列只包含當前元素，長度為1dp[i][0] = 1;dp[i][1] = 1;// 檢查前面所有元素，看是否可以形成更長的有效子序列for (int j = 0; j < i; j++) {// 計算nums[j]和nums[i]之和的奇偶性int sumMod = (nums[j] + nums[i]) % 2;// 如果前面元素j和當前元素i的和的奇偶性為sumMod// 則可以將i添加到以j結尾的sumMod類型子序列后面if (dp[j][sumMod] + 1 > dp[i][sumMod]) {dp[i][sumMod] = dp[j][sumMod] + 1;}}// 更新最長有效子序列長度maxLen = Math.max(maxLen, Math.max(dp[i][0], dp[i][1]));}return maxLen;}
}

復雜度分析：

時間復雜度：O(n2)，其中 n 是數組長度
空間復雜度：O(n)，需要存儲 dp 數組

🚀 優化后的貪心算法

我們可以進一步優化貪心算法，只需要一次遍歷就能計算出兩種類型 1 子序列的最大長度：

/*** 方法四：優化后的貪心算法* 思路：在基礎貪心算法的基礎上，通過一次遍歷同時計算兩種類型1子序列的長度*       減少了遍歷次數，進一步優化了性能* 時間復雜度：O(n)，空間復雜度：O(1)*/
public class Solution {/*** 找出最長有效子序列的長度* @param nums 輸入的整數數組* @return 最長有效子序列的長度*/public int maximumLength(int[] nums) {int n = nums.length;// 邊界情況處理：空數組或單元素數組，直接返回數組長度if (n <= 1) return n;// 統計數組中奇數和偶數的個數int oddCount = 0, evenCount = 0;for (int num : nums) {if (num % 2 == 0) evenCount++;else oddCount++;}// 類型0的最大長度：所有元素奇偶性相同，取較多的那種int type0Max = Math.max(oddCount, evenCount);// 如果只有一種奇偶性，無法形成類型1的子序列（需要交替出現）if (oddCount == 0 || evenCount == 0) {return type0Max;}// 一次遍歷同時計算兩種類型1子序列的最大長度int type1OddStart = 0;  // 以奇數開始的交替序列長度（奇-偶-奇-偶...）int type1EvenStart = 0; // 以偶數開始的交替序列長度（偶-奇-偶-奇...）boolean expectOddForOddStart = true;  // 奇開始模式下期望的下一個奇偶性boolean expectOddForEvenStart = false; // 偶開始模式下期望的下一個奇偶性// 遍歷數組，同時構建兩種交替模式的子序列for (int num : nums) {boolean isOdd = num % 2 == 1; // 當前元素是否為奇數// 處理奇-偶-奇-偶...模式if (isOdd == expectOddForOddStart) {type1OddStart++;expectOddForOddStart = !expectOddForOddStart; // 切換期望的奇偶性}// 處理偶-奇-偶-奇...模式if (isOdd == expectOddForEvenStart) {type1EvenStart++;expectOddForEvenStart = !expectOddForEvenStart; // 切換期望的奇偶性}}// 類型1的最大長度為兩種模式中的較大值int type1Max = Math.max(type1OddStart, type1EvenStart);// 返回兩種類型中的最大值return Math.max(type0Max, type1Max);}
}