Given an array write C# program to find the sum of all the possible sub-arrays.

For.e.g.

int [] a = {4, 2, 1};

Output: Possible subarrays –

{4}, {2}, {1}, {4, 2}, {2, 1}, {4, 2, 1}

So, sum = 4+ 2+ 1 + 6 + 3 + 7 = 23

Solution

Brute force approach

Problem with below program is iterating over all pairs of (start, stop), then iterate over all the elements in the subarray defined by that range. To compute the sub array, it will take O(n3) time.

using System; 
namespace SubArraySum
{    
    class Program
    {
        
        static void Main()
        {
            Console.WriteLine("Enter array length");
            var n = Convert.ToInt32(Console.ReadLine());
            var arr = new int[n];
            Console.WriteLine("Enter array elements");
            for (var i = 0; i < n; i++)
            {
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            var sum = FindSum(arr);
            Console.WriteLine($"Sum of elements of sub arrays is: {sum}");
        }
                
        static int FindSum(int[] arr)
        {
            var totalSum = 0;
            for (var i = 0; i < arr.Length; i++)
            {
                for (var j = i; j <= arr.Length; j++)
                {
                    for (var k = i; k < j; k++)
                    {
                        totalSum += arr[k];
                    }
                }
            }
            return totalSum;
        }
    }
}

Here is better approach to resolve the above program with O(n) Time

The basic idea behind the approach is to compute the sum, but not in the order intended. For example, look at the array [4, 2, 1]. The subarrays are

[4] [2] [1] [4, 2] [2, 1] [4, 2, 1]

Notice how many copies of each element there are. 

There are three 4’s , four 2’s and three 1’s. so to compute the above sum we just need to efficiently compute how many copies of each element there are across all the different subarrays, we could directly compute the sum by multiply each element in the array by the number of times it appears across all the subarrays and then adding them up.

To count occurrence of array

The first element of the array will appear in n different subarrays each of them starts at the first position.

The second element of the array will appear in n­1 subarrays that begin at its position, plus n­-1 subarrays from the previous position

The third element of the array will appear in n-2 subarrays that begin in its position, plus n-2 subarrays beginning at the first element (all n arrays, minus the one of length two and the one of length one) and n-2 subarrays beginning at the second element (all n-1 of them except for the one of length one). More generally, the ith element will open n – i new intervals (one for each length stretching out to the end) and, for each preceding element, will overlap n – i of the intervals starting there. This means that the total number of intervals overlapping element i is given by

(n – i)i + (n – i) = (n – i)(i + 1)

using System;
namespace SubArraySum
{
    class Program
    {
        static void Main()
        {
            Console.WriteLine("Enter array length");
            var n = Convert.ToInt32(Console.ReadLine());
            var arr = new int[n];
            Console.WriteLine("Enter array elements");
            for (var i = 0; i < n; i++)
            {
                arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            var sum = FindSum(arr);
            Console.WriteLine($"Sum of elements of sub arrays is: {sum}");
            Console.ReadLine();
        }
                
                
        static int FindSum(int[] arr)
        {
            var n = arr.Length;
            var totalSum = 0;
            for (var i = 0; i < n; i++)
            {
                totalSum += arr[i] * (n - i) * (i + 1);
            }
            return totalSum;
        }
    }
}