Given an array of positive integers, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.
Example,
arr = [1, 4, 2, 5, 3]
The odd-length subarrays of arr and their sums are:
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1, 4, 2] = 7
[4, 2, 5] = 11
[2, 5, 3] = 10
[1, 4, 2, 5, 3] = 15
If we add all these together we get 1+4+2+5+3+7+11 = 58
Approach:
From Subarray Sums the occurrences we can divide by 2 and can take it to calculate the odd length subarray sum.
Simply by traversing the whole array we can do,
occurences = ((i + 1) * (n - i))
result += (arr[i] * ( (occurences + 1)/ 2 ) ) // taking ceil
No comments:
Post a Comment