Sum of All Odd Length Subarrays
Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.
A subarray is a contiguous subsequence of the array.
Follow up: Could you solve this problem in O(n) time complexity?
Example 1
Input
arr = [1,4,2,5,3]Output
58The odd-length subarrays have sums 1, 4, 2, 5, 3, 7, 11, 10, and 15, which add up to 58.
Example 2
Input
arr = [1,2]Output
3There are only two subarrays of odd length, [1] and [2], and their sum is 3.
Constraints
- 1 <= arr.length <= 100
- 1 <= arr[i] <= 1000