1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int sum = 0;
int[] prefixSums = new int[arr.length + 1];
for (int i = 1; i < prefixSums.length; i++) {
prefixSums[i] = prefixSums[i - 1] + arr[i - 1];
for (int j = 1; i - j >= 0; j += 2) {
sum += prefixSums[i] - prefixSums[i - j];
}
}
return sum;
}
}
|
References
1588. Sum of All Odd Length Subarrays