How to find the sum of all subarrays in Python
A subarray is a contiguous part of an array. For example {4, 6, 2 ,8} is an array of 4 elements. If we suppose the first 3 elements of the array as {4, 6, 2}, then it is a subarray of the array {4, 6, 2, 8}. But if we assume {4, 6, 8}, this is not a subarray of {4, 6, 2 ,8} because the elements are not contiguous.
Example
Given an array find the sum of all possible subarrays.
The possible subarrays for the given array are:
We have 1 subarray array of length 4.
We have 2 subarrays of lengths 3.
We have 3 subarrays of length 2.
We have 4 subarrays of length 1.
Algorithm intuition
In the array arr[i], every number has two subarrays:
In subarrays beginning with arr[i], there are (n-i) such subarrays. For example, number [2] appears in subarray [2] and subarray [2, 3].
In (n-i)*i subarrays where this element is not the first element. For example [2] appears in [1, 2] and [1, 2, 3].
Example
def SubArraySum(arr, n ):result = 0for i in range(0, n):result = result + (arr[i] * (i+1) * (n-i))return resultarr = [1, 2, 3, 4]n = len(arr)print ("Sum of all SubArrays : ",SubArraySum(arr, n))
Explanation
-
Line 1: The
def SubArraySum()function is used to compute the sum of all subarrays. -
Line 4: Computing the sum of a subarray using formula
result = result + (arr[i] * (i+1) * (n-i)). We are counting the number of subarrays that overlap a particular element at indexiby counting those subarrays and focusing on the index at which those subarrays start. The first element of the array will appear inndifferent subarrays and each of them starts at the first position. The second element of the array will appear inn-1subarrays that begin at its position, plusn-1subarrays from the previous position. The total number of intervals overlapping element i is given by:(n – i) * i + (n – i) = (n – i) * (i + 1). -
Line 5: Returns the sum of all subarrays.
-
Line 6–9: Driver function for a given array.
Free Resources