3284. Sum of Consecutive Subarrays π
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 subarrays.
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,3]
Output: 20
Explanation:
The consecutive subarrays are: [1]
, [2]
, [3]
, [1, 2]
, [2, 3]
, [1, 2, 3]
.
Sum of their values would be: 1 + 2 + 3 + 3 + 5 + 6 = 20
.
Example 2:
Input: nums = [1,3,5,7]
Output: 16
Explanation:
The consecutive subarrays are: [1]
, [3]
, [5]
, [7]
.
Sum of their values would be: 1 + 3 + 5 + 7 = 16
.
Example 3:
Input: nums = [7,6,1,2]
Output: 32
Explanation:
The consecutive subarrays are: [7]
, [6]
, [1]
, [2]
, [7, 6]
, [1, 2]
.
Sum of their values would be: 7 + 6 + 1 + 2 + 13 + 3 = 32
.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Solutions
Solution 1: Recurrence
We define two variables $f$ and $g$, representing the length of the increasing subarray ending at the current element and the length of the decreasing subarray ending at the current element, respectively. We use two other variables $s$ and $t$ to represent the sum of the increasing subarray ending at the current element and the sum of the decreasing subarray ending at the current element, respectively. Initially, $f = g = 1$, and $s = t = \textit{nums}[0]$.
Next, we traverse the array starting from the second element. For the current element $\textit{nums}[i]$, we consider the increasing subarray and the decreasing subarray ending at $\textit{nums}[i]$.
If $\textit{nums}[i] - \textit{nums}[i - 1] = 1$, then $\textit{nums}[i]$ can be added to the increasing subarray ending at $\textit{nums}[i - 1]$. In this case, we update $f$ and $s$, and add $s$ to the answer.
If $\textit{nums}[i] - \textit{nums}[i - 1] = -1$, then $\textit{nums}[i]$ can be added to the decreasing subarray ending at $\textit{nums}[i - 1]$. In this case, we update $g$ and $t$, and add $t$ to the answer.
Otherwise, $\textit{nums}[i]$ cannot be added to the increasing or decreasing subarray ending at $\textit{nums}[i - 1]$. We add $\textit{nums}[i]$ to the answer.
After the traversal, return the answer.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
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 |
|
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 |
|
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 37 38 39 40 41 |
|
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 37 |
|