Prefix Sum
Prefix Sum
1588. Sum of All Odd Length Subarrays
- better solution is math
def sumOddLengthSubarrays(arr): accum = 0 prefix_sum = [0] for num in arr: accum += num prefix_sum.append(accum) total = 0 for l in range(1, len(arr) + 1): for r in range(l, len(arr) + 1): if (r - l + 1) % 2 == 1: total += prefix_sum[r] - prefix_sum[l - 1] return total