Problem Description

We define an array arr of length n as consecutive if it satisfies one of the following conditions:

• arr[i] - arr[i - 1] == 1 for all 1 <= i < n.
• arr[i] - arr[i - 1] == -1 for all 1 <= i < n.

The value of an array is the sum of its elements.

For example, [3, 4, 5] is a consecutive array with a value of 12, and [9, 8] is another consecutive array with a value of 17. In contrast, [3, 4, 3] and [8, 6] are not consecutive.

Given an array of integers nums, return the sum of the values of all consecutive non-empty subsequences.

Since the result may be very large, return it modulo (10^9 + 7).

Note that an array of length 1 is also considered consecutive.

Intuition

To solve this problem, the key is to determine how often each element in nums contributes to a consecutive subsequence of length greater than 1.

1. Understanding Contributions: Each element nums[i] contributes to the value of consecutive subsequences. By calculating how many such subsequences include nums[i], we can determine its contribution.

2. Identifying Patterns: We focus on two main patterns: strictly increasing and strictly decreasing subsequences.

3. Two-Pass Calculation: For each pattern, we use two arrays, left and right, to track potential subsequences:

   • Left Array: This array tracks the number of strictly increasing subsequences ending just before the current element.
   • Right Array: This array tracks the number of strictly increasing subsequences starting right after the current element.

4. Total Calculation for Subsequence Contributions: By computing these patterns separately using a function calc(nums), and reversing the array to handle both increasing and decreasing subsequences, we can calculate the overall sum by:

   • Calculating contributions for strictly increasing subsequences.
   • Reversing the array to calculate contributions for strictly decreasing subsequences.
   • Adding the total contribution from all elements.

Through these steps, the solution efficiently processes the array nums, combining contributions from all possible consecutive subsequences to deliver the desired result.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution utilizes an enumeration technique to determine the contribution of each element in the array nums to the sum of all possible consecutive subsequences. Below is a detailed explanation of the approach used:

1. Contributions Calculation:

   • We need to figure out how frequently each nums[i] appears in consecutive subsequences longer than 1. The contribution of an element in such subsequences is the product of its frequency and its value.

2. Calc Function:

   • A function calc(nums) is implemented to compute the contributions for a given ordering (strictly increasing or decreasing). This function helps calculate the sum of values of all subsequences that are consecutive.

3. Two Supporting Arrays:

   • left: This array is used to count how many strictly increasing subsequences end with the element nums[i] - 1 before each nums[i].
   • right: This array counts how many strictly increasing subsequences start with the element nums[i] + 1 after each nums[i].

4. Implementation Steps in calc(nums):

   • Initialize two arrays left and right filled with zeros.
   • Use a counter to determine the number of subsequences ending with nums[i] - 1 as you traverse the list.
   • Traverse from left to right and update left array.
   • Reset the counter and traverse from right to left to fill the right array.

5. Combining Results:

   • First, calculate contributions using calc(nums) for strictly increasing subsequences.
   • Reverse nums and calculate contributions again for strictly decreasing subsequences.
   • Add the sum of all elements from the original array for subsequences of length 1.

6. Modulo Operation:

   • The final computed sum needs to be returned modulo (10^9 + 7) to manage large number overflow.

This approach ensures that the solution is efficient, incorporating both directions of sequence formation with a complexity of ( O(n) ).

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have an array nums = [2, 3, 2, 1]. We need to find the sum of values of all consecutive non-empty subsequences, where the conditions for consecutiveness are defined by the difference being 1 or -1 between consecutive elements.

Step 1: Identify Consecutive Subsequences

• Based on the definitions, identify all non-empty consecutive subsequences:
  • Increasing subsequences: [2, 3] (value 5), and [2, 3, 2] (value 7)
  • Decreasing subsequences: [3, 2] (value 5), [3, 2, 1] (value 6), and [2, 1] (value 3)
  • Each individual element is also a consecutive subsequence by itself: [2], [3], [2], [1] with values 2, 3, 2, and 1 respectively.

Step 2: Calculate Values Using the Calc Function

• Increasing Order Contributions: Using the calc(nums) function for strictly increasing subsequences:

  • left array represents subsequences ending at each index: [0, 1, 1, 0]
  • right array represents subsequences starting at each index: [1, 0, 0, 0]
  • Calculate contributions for increasing sequences: using these arrays and summing corresponding subsequences' values.

• Decreasing Order Contributions: Reverse nums to handle the strictly decreasing subsequences: Using the calc(nums) function for strictly decreasing subsequences:

  • nums reversed: [1, 2, 3, 2]
  • left array updated after reversal: [0, 1, 1, 0]
  • right array updated after reversal: [0, 1, 0, 0]
  • Calculate contributions for decreasing sequences.

Step 3: Combine Results

• Include the contribution of each subsequence:
  • Sum contributions from both increasing and decreasing subsequences.
  • Add values of each single-element subsequence: [2], [3], [2], and [1].

Step 4: Apply Modulo Operation

• Compute the total sum of contributions and take modulo (10^9 + 7) to ensure manageable output size.

Thus, by following these steps, we manage to efficiently calculate the sum of the values of all consecutive subsequences in nums, giving us the final result.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the function calc iterates over the list nums twice in two separate loops, each running in O(n) time. Additionally, the zip and sum functions are applied on lists of size n, which also run in O(n) time. Since these operations are done in sequence, the overall time complexity remains O(n).

The space complexity of the code is O(n), due to the additional data structures used. Specifically, two lists left and right of size n are created. Moreover, the Counter object stores data proportional to the number of unique elements in nums, which, in the worst case, could lead to an additional space complexity of O(n). Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.