3299. Sum of Consecutive Subsequences π
Description
We call an array arr
of length n
consecutive if one of the following holds:
arr[i] - arr[i - 1] == 1
for all1 <= i < n
.arr[i] - arr[i - 1] == -1
for all1 <= i < n
.
The value of an array is the sum of its elements.
For example, [3, 4, 5]
is a consecutive array of value 12 and [9, 8]
is another of value 17. While [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 answer may be very large, return it modulo 109 + 7.
Note that an array of length 1 is also considered consecutive.
Example 1:
Input: nums = [1,2]
Output: 6
Explanation:
The consecutive subsequences are: [1]
, [2]
, [1, 2]
.
Example 2:
Input: nums = [1,4,2,3]
Output: 31
Explanation:
The consecutive subsequences are: [1]
, [4]
, [2]
, [3]
, [1, 2]
, [2, 3]
, [4, 3]
, [1, 2, 3]
.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Solutions
Solution 1: Enumeration of Contributions
Let us count how many times each element $\textit{nums}[i]$ appears in a continuous subsequence of length greater than 1. Then, multiplying this count by $\textit{nums}[i]$ gives the contribution of $\textit{nums}[i]$ in all continuous subsequences of length greater than 1. We sum these contributions, and adding the sum of all elements, we get the answer.
We can first compute the contribution of strictly increasing subsequences, then the contribution of strictly decreasing subsequences, and finally add the sum of all elements.
To implement this, we define a function $\textit{calc}(\textit{nums})$, where $\textit{nums}$ is an array. This function returns the sum of all continuous subsequences of length greater than 1 in $\textit{nums}$.
In the function, we can use two arrays, $\textit{left}$ and $\textit{right}$, to record the number of strictly increasing subsequences ending with $\textit{nums}[i] - 1$ on the left of each element $\textit{nums}[i]$, and the number of strictly increasing subsequences starting with $\textit{nums}[i] + 1$ on the right of each element $\textit{nums}[i]$. In this way, we can calculate the contribution of $\textit{nums}$ in all continuous subsequences of length greater than 1 in $O(n)$ time complexity.
In the main function, we first call $\textit{calc}(\textit{nums})$ to compute the contribution of strictly increasing subsequences, then reverse $\textit{nums}$ and call $\textit{calc}(\textit{nums})$ again to compute the contribution of strictly decreasing subsequences. Finally, adding the sum of all elements gives the answer.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|