3686. Number of Stable Subsequences
Description
You are given an integer array nums.
A subsequence is stable if it does not contain three consecutive elements with the same parity when the subsequence is read in order (i.e., consecutive inside the subsequence).
Return the number of stable subsequences.
Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,3,5]
Output: 6
Explanation:
- Stable subsequences are
[1],[3],[5],[1, 3],[1, 5], and[3, 5]. - Subsequence
[1, 3, 5]is not stable because it contains three consecutive odd numbers. Thus, the answer is 6.
Example 2:
Input: nums = [2,3,4,2]
Output: 14
Explanation:
- The only subsequence that is not stable is
[2, 4, 2], which contains three consecutive even numbers. - All other subsequences are stable. Thus, the answer is 14.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Solutions
Solution 1
Thinking
A stable subsequence forbids a too-long run of the same parity. \(n\le 10^5\) needs a linear DP.
Let states distinguish the last parity and whether the current run has length \(1\) or \(2\); a run of \(3\) is illegal.
A new \(x\) may follow the opposite parity, or the same parity when the run is still shorter than \(2\). Reduce modulo \(10^9+7\) and sum every legal state.
1 | |
1 | |
1 | |
1 | |