We call an array arr of length n consecutive if one of the following holds:
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 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] <= 105We 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 = nums[0].
Next, we traverse the array starting from the second element. For the current element nums[i], we consider the increasing subarray and the decreasing subarray ending at nums[i].
If nums[i] - nums[i - 1] = 1, then nums[i] can be added to the increasing subarray ending at nums[i - 1]. In this case, we update f and s, and add s to the answer.
If nums[i] - nums[i - 1] = -1, then nums[i] can be added to the decreasing subarray ending at nums[i - 1]. In this case, we update g and t, and add t to the answer.
Otherwise, nums[i] cannot be added to the increasing or decreasing subarray ending at nums[i - 1]. We add 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).
Java
C++
Go
TypeScript
Longest Consecutive Sequence - Leetcode 128 • NeetCode • 904,099 views views
Watch 9 more video solutions →Practice Sum of Consecutive Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor