Hard
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:
[1]
, [3]
, [5]
, [1, 3]
, [1, 5]
, and [3, 5]
.[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:
[2, 4, 2]
, which contains three consecutive even numbers.Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
public class Solution {
private static final long MOD = 1000000007L;
public int countStableSubsequences(int[] nums) {
long e1 = 0;
long e2 = 0;
long o1 = 0;
long o2 = 0;
for (int x : nums) {
if ((x & 1) == 0) {
long ne1 = (e1 + (o1 + o2 + 1)) % MOD;
long ne2 = (e2 + e1) % MOD;
e1 = ne1;
e2 = ne2;
} else {
long no1 = (o1 + (e1 + e2 + 1)) % MOD;
long no2 = (o2 + o1) % MOD;
o1 = no1;
o2 = no2;
}
}
long ans = (e1 + e2 + o1 + o2) % MOD;
return (int) ans;
}
}