In this blog post, we learn how to write a C program to find the sum of all sub-array sums for a given array? So here we will write the C program to find the sum of all sub-array sums for a given array. We will also see how to display the sum of all sub-array sums for a given array using C programming.
Example,
//Given array
Input : arr[] = {1, 3, 5}
Output: 30
Explanation: All possible sub-array sum is:
(1) + (3) + (5) + (1+3) + (3+5) + (1+3+5) => 30
Note: A sub-array is a contiguous part of the array. In the above example {1,5} is not a subarray because they’re not consecutive in the array.
So let’s see the logic to find the sum of all sub-array sums for a given array. Suppose arr is an integer array of size N (arr[N] ), the task is to write the C program to find the sum of all sub-array sum for a given array.
Method 1: By Generating sub array
This method is very simple to calculate the sum of sub-array, in which we will just list off all the subarrays and add all of them up. We can implement this using the triple loop, where we will iterate over all pairs of (start, stop). This technique is very poor and there are several observations. The time complexity of this solution is O(n^3).
#include <stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
// Computes sum all sub-array
long int subArraySum(int arr[], int n)
{
long int result = 0;
int i =0,j=0, k= 0;
// Pick starting point
for (i=0; i <n; i++)
{
// Pick ending point
for (j=i; j<n; j++)
{
for (k = i ; k <= j ; k++)
{
result += arr[k];
}
}
}
return result ;
}
int main()
{
int arr[] = { 1,3,5};
//Get array size
int n = ARRAY_SIZE(arr);
//Get sum of all sub array
long int sum = subArraySum(arr, n) ;
printf("Sub Array Sum = %d\n",sum);
return 0;
}
Output:
If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.
Your free trial is waiting
Method 2: Optimized Subarray Enumeration
We can optimize the first solution using the below technique. So let’s see the technique to how we can increase the performance of the above solution.
If you know the sum of the subarray from index ‘i’ to index ‘j’, then then the sum of the subarray from index ‘i’ to index j+1 can be formed by taking the sum of the original subarray, then adding arr[j+1] into the total. The time complexity of this solution is O(n^2).
Example,
//Assumed input integer array
int arr[] = {1,2,3,4,5}
subArray1 > {1,2} and sum is (1+2) => 3
subArray2 > {1,2,3} and sum is (1+2+3) => 6
We can also calculate the sum of subArray2 using the above-described technique.
subArray2 => subArray1 + arr[2] > 3 + 3 > 6
#include <stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
// Computes sum all sub-array
long int subArraySum(int arr[], int n)
{
long int result = 0,temp=0;
int i =0,j=0;
// Pick starting point
for (i=0; i <n; i++)
{
temp=0;
// Pick ending point
for (j=i; j<n; j++)
{
// sum subarray between current
// starting and ending points
temp+=arr[j];
result += temp ;
}
}
return result ;
}
int main()
{
int arr[] = {1,3,5} ;
//Get array size
int n = ARRAY_SIZE(arr);
//Get sum of all sub array
long int sum = subArraySum(arr, n) ;
printf("Sub Array Sum = %d\n",sum);
return 0;
}
Output:
Method 3: Subarray sum using pattern technique
In all mentioned techniques it is the most optimized algorithm to calculate the sum of the subarray. The basic idea behind the approach is to compute the sum, but not in the order intended. For example, take a look at the array [1, 2, 3]. The subarrays are:
//Subarrays of an array {1,2,3},
[1] [2] [3]
[1, 2] [2, 3]
[1, 2, 3]
Now, notice how many copies of each element there are. There are three 1’s, four 2’s, and three 3’s.
here first element 'arr[0]' appears 3 times
second element 'arr[1]' appears 4 times
third element 'arr[2]' appears 3 times
If we could 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.
If you will analyze the pattern you will find that every element arr[i] appears in two types of subsets:
- In subarrays beginning with arr[i]. There are (n-i) such subsets. For example [2] appears in [2] and [2, 3].
- In (n-i)*i subarrays where this element is not first element. For example [2] appears in [1, 2] and [1, 2, 3].
This means that the total number of intervals overlapping element i is given by,
total number of ith element = (n-i) + (n-i)*i;
= (n-i)(i+1);
where n is the size of the array.
#include <stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
long int subArraySum( int arr[], int n )
{
long int result = 0;
int i =0;
// computing sum of sub array using formula
for (i=0; i<n; i++)
{
result += (arr[i] * (i+1) * (n-i));
}
return result ;
}
int main()
{
int arr[] = {1,3,5} ;
//Get array size
int n = ARRAY_SIZE(arr);
//Get sum of all sub array
long int sum = subArraySum(arr, n) ;
printf("Sub Array Sum = %d\n",sum);
return 0;
}
Output:
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
- How to access 2d array in C?
- Dangling, Void, Null and Wild Pointers
- Function pointer in c, a detailed guide
- How to use the structure of function pointer in c language?
- Memory Layout in C.
- 100 C interview Questions
- File handling in C.
- C format specifiers.
7 comments