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