LC 1588 [E] Sum of All Odd Length Subarrays - ALawliet/algorithms GitHub Wiki
this is NOT an easy problem to get the optimal O(n) solution... it's a math trick
https://www.youtube.com/watch?v=J5IIH35EBVE&ab_channel=NateSantti
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
res = 0
n = len(arr)
for i in range(n):
end = i + 1
start = n - i
total = start * end
odd = total // 2
if total % 2 == 1:
odd += 1
res += odd * arr[i]
return res