1588. Sum of All Odd Length Subarrays
Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.
Return the sum of all odd-length subarrays of arr.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
if(arr.size() <= 2) return accumulate(arr.begin(),arr.end(),0);
int sum = arr[0] + arr[1], prevSum = arr[1], prevPrevSum = arr[0];
for(int i = 2; i < arr.size(); i++) {
prevPrevSum += (arr[i-1] + arr[i]) * (i / 2) + arr[i];
sum += prevPrevSum;
swap(prevPrevSum, prevSum);
}
return sum;
}
};
|
