116. Sum of All Subarray Sums
Challenge1000 ms256 MBSolved by 0%
Add up the sums of every contiguous subarray and print the total.
For [1, 2, 3] the subarrays are [1], [2], [3], [1,2], [2,3], [1,2,3],
whose sums are 1, 2, 3, 3, 5, 6, a total of 20.
There are about n²/2 subarrays, so building them one at a time is not the intended route.
Constraints - `1 ≤ n ≤ 200000` - `-1000000 ≤ a[i] ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer, the total of the sums of every contiguous subarray.
Input3
1 2 3
Output20
Noteis the worked example from the statement
Input1
5
Output5
Notehas one subarray, which is the element itself
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.