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] == 1for all1 <= i < n.arr[i] - arr[i - 1] == -1for 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 <= 1051 <= 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)$.
Python3ο
class Solution:
def getSum(self, nums: List[int]) -> int:
mod = 10**9 + 7
f = g = 1
s = t = nums[0]
ans = nums[0]
for x, y in pairwise(nums):
if y - x == 1:
f += 1
s += f * y
ans = (ans + s) % mod
else:
f = 1
s = y
if y - x == -1:
g += 1
t += g * y
ans = (ans + t) % mod
else:
g = 1
t = y
if abs(y - x) != 1:
ans = (ans + y) % mod
return ans
Javaο
class Solution {
public int getSum(int[] nums) {
final int mod = (int) 1e9 + 7;
long s = nums[0], t = nums[0], ans = nums[0];
int f = 1, g = 1;
for (int i = 1; i < nums.length; ++i) {
int x = nums[i - 1], y = nums[i];
if (y - x == 1) {
++f;
s += 1L * f * y;
ans = (ans + s) % mod;
} else {
f = 1;
s = y;
}
if (y - x == -1) {
++g;
t += 1L * g * y;
ans = (ans + t) % mod;
} else {
g = 1;
t = y;
}
if (Math.abs(y - x) != 1) {
ans = (ans + y) % mod;
}
}
return (int) ans;
}
}
C++ο
class Solution {
public:
int getSum(vector<int>& nums) {
const int mod = 1e9 + 7;
long long s = nums[0], t = nums[0], ans = nums[0];
int f = 1, g = 1;
for (int i = 1; i < nums.size(); ++i) {
int x = nums[i - 1], y = nums[i];
if (y - x == 1) {
++f;
s += 1LL * f * y;
ans = (ans + s) % mod;
} else {
f = 1;
s = y;
}
if (y - x == -1) {
++g;
t += 1LL * g * y;
ans = (ans + t) % mod;
} else {
g = 1;
t = y;
}
if (abs(y - x) != 1) {
ans = (ans + y) % mod;
}
}
return ans;
}
};
Goο
func getSum(nums []int) int {
const mod int = 1e9 + 7
f, g := 1, 1
s, t := nums[0], nums[0]
ans := nums[0]
for i := 1; i < len(nums); i++ {
x, y := nums[i-1], nums[i]
if y-x == 1 {
f++
s += f * y
ans = (ans + s) % mod
} else {
f = 1
s = y
}
if y-x == -1 {
g++
t += g * y
ans = (ans + t) % mod
} else {
g = 1
t = y
}
if abs(y-x) != 1 {
ans = (ans + y) % mod
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
TypeScriptο
function getSum(nums: number[]): number {
const mod = 10 ** 9 + 7;
let f = 1,
g = 1;
let s = nums[0],
t = nums[0];
let ans = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i - 1];
const y = nums[i];
if (y - x === 1) {
f++;
s += f * y;
ans = (ans + s) % mod;
} else {
f = 1;
s = y;
}
if (y - x === -1) {
g++;
t += g * y;
ans = (ans + t) % mod;
} else {
g = 1;
t = y;
}
if (Math.abs(y - x) !== 1) {
ans = (ans + y) % mod;
}
}
return ans;
}