Subarray Sums

Problem:

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

For example, the array [1, 3, 7] has seven subarrays(N*(N+1)/2):

[ ]    [1]   [3]   [7]   [1, 3]   [3, 7]   [1, 3, 7]

Notice that [1, 7] is not a subarray of [1, 3, 7], because even though the values 1 and 7 appear

in the array, they're not consecutive in the array. Similarly, the array [7, 3] isn't a

subarray of the original array, because these values are in the wrong order.

The sum of an array is the sum of all the values in that array. Your task is to write a function that takes as input an array and outputs the sum of all of its subarrays.

For example, given [1, 3, 7], you'd output 36, because

[ ] + [1] + [3] + [7] + [1, 3] + [3, 7] + [1, 3, 7] = 0 + 1 + 3 + 7 + 4 + 10 + 11 = 36

Approach:

The problem is very easy to understand. Now First, try to solve this by the brute force approach. 

Here we visit every length subarray, this will cost O(n^3), which is huge. We can reduce it to O(n^2), but that's not enough.

We can improve our time complexity by a little observastion, just think about every numbers occurences in their total subarray's.

Just look at the array [1,2,3], subarray's are,

[1] [2] [3]

[1,2] [2,3]

  [1,2,3]

Notice how many copies of each element there are. There are three 1's, four 2's, and three 3's.



Occurences can be calculate by simple formula (i + 1) * (arr.length() - i)
So, By traversing the whole array we can calcualte our subarray sum by this formula
result += arr[i] * (i + 1) * (arr.length() - i)