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.
Example 1:
Input: nums = [1,2,1]
Output: 14
Explanation:
[1], [2], [1], [1,2], [2,1], [1,2,1].Example 2:
Input: nums = [3,4,5]
Output: 40
Explanation:
[3], [4], [5], [3,4], [4,5], [3,4,5].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105This approach involves generating all subsequences of the given array and checking if each subsequence is good, i.e., consecutive elements have an absolute difference of 1.
Once we identify a good subsequence, we calculate the sum of its elements. We take care of possible overflows by applying the modulus operation with 10^9 + 7 after every addition.
Though simple, this approach is inefficient for large arrays due to its exponential time complexity.
The code defines a helper function valid_sequence to check if a subsequence is good. Another helper subsequences generates all subsequences of the list recursively. It computes the total sum of elements in all good subsequences and returns it.
JavaScript
Time Complexity: O(2^n * n), where n is the length of the array, due to generating all subsequences. Space Complexity: O(2^n), due to storing all subsequences.
Instead of generating all subsequences, we can opt for a more efficient approach using dynamic programming.
Create a frequency array to count occurrences of each element. Iterate through possible values, updating a dp array, which keeps the sum of all subsequences ending with a particular value.
For each number i, you can either start a subsequence or extend subsequences ending with i-1, i, or i+1, respecting the absolute difference constraint.
Modulo operation ensures we handle large numbers properly.
This Python code utilizes an array dp that stores cumulative subsequences sums ending at each number. We update our dp array based on current frequency and potential pre-existing subsequences.
Java
Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(2^n * n), where n is the length of the array, due to generating all subsequences. Space Complexity: O(2^n), due to storing all subsequences. |
| Dynamic Programming Approach | Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value). |
Maximum Subarray - Kadane's Algorithm -- Leetcode 53 • Greg Hogg • 367,081 views views
Watch 9 more video solutions →Practice Sum of Good Subsequences with our built-in code editor and test cases.
Practice on FleetCode