You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1.
Return the sum of all possible good subsequences of nums.
Since the answer may be very large, return it modulo 109 + 7.
Note that a subsequence of size 1 is considered good by definition.
Examples
Example 1
Input: nums = [1,2,1]
Output: 14
Explanation:
Example 2
Input: nums = [3,4,5]
Output: 40
Explanation:
Constraints
1 <= nums.length <= 105
0 <= nums[i] <= 105
3351. Sum of Good Subsequences
Hard
50 Points
Array
Hash Table
Dynamic Programming
You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1.
Return the sum of all possible good subsequences of nums.
Since the answer may be very large, return it modulo 109 + 7.
Note that a subsequence of size 1 is considered good by definition.
Examples
Example 1
Input: nums = [1,2,1]
Output: 14
Explanation:
Example 2
Input: nums = [3,4,5]
Output: 40
Explanation:
Constraints
1 <= nums.length <= 105
0 <= nums[i] <= 105
Sum of Good Subsequences - Practice Coding | SlaveCode