C Program to Find the Sum of Contiguous Subarray within a 1 – D Array of Numbers which has the Largest Sum

«
»

This is a C Program to find the sum of contiguous subarray within a 1 – D array of numbers which has the largest sum.

Problem Description

We have to write a program in C such that the program will find the sum of contiguous subarray within a 1 – D array of numbers (one-dimensional array of numbers) which has the largest sum.

Suppose, we have an array of 8 elements with values: -1,-5,5,3,-2,5,4 and 1, then here is a sample of various possible contiguous subarrays:

advertisement
-1
-1,-5
-1,-5,5
-1,-5,5,3
-1,-5,5,3,-2
-1,-5,5,3,-2,5
-1,-5,5,3,-2,5,4
-1,-5,5,3,-2,5,4,1
-5
-5,5
-5,5,3
....
....
....

For each subarray, we have to do the sum of the elements of the subarray and then find the subarray which has the largest sum.

Expected Input and Output

If we are entering 8 elements (N = 8), with array element values as -1,-5,5,3,-2,5,4 and 1 then,
The largest contiguous subarray is: 5 3 -2 5 4 1
The sum of the largest contiguous subarray is: 16

Problem Solution

In this program, we will print the contiguous subarray within one dimensional array of numbers which has the largest sum.

We will do this by iterating over every possible contiguous combination of the array using 2 for loops.

advertisement

Then we will compare them to a variable largest which is initialized with a value of first element of the array, say array[0]. For every contiguous subarray, we will add the elements of that subarray and then compare it with the variable largest to find the largest sum and also store the address of the starting and ending index.

In the end, we will print the Largest sum and the corresponding subarray.

The sequence of steps for the solution will be as follows:
1. Create an array of user-defined size.
2. Run a for loop to read the elements of the array.
3. Considering the first element of the array to be the largest, compare all the contiguous subarray sums, and change the largest value if the largest element is smaller than the current subarray sum.
4. At last, the largest element will hold the actual largest contiguous subarray sum and then print it.

Program/Source Code

Here is the source code of the C Program to find the sum of contiguous subarray within a 1 – D array of numbers which has the largest sum. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. /*
  2.  * C Program to Find the Sum of Contiguous Subarray within a 
  3.  * 1 - D Array of Numbers which has the Largest Sum
  4.  */
  5.  
  6. #include<stdio.h>
  7.  
  8. int main()
  9. {
  10.     int size,m=0,l=0;
  11.  
  12.     printf("Type the length of the array\n");
  13.     scanf("%d",&size);
  14.     int array[size];
  15.     printf("type the elements of the array\n");
  16.  
  17.     for(int i=0;i<size;i++)
  18.     {
  19.         scanf("%d",&array[i]);
  20.  
  21.     }
  22.  
  23.     int largest=array[0];
  24.     for(int i=0;i<size;i++)
  25.     {
  26.         int sum=0;
  27.         for(int j=i;j<size;j++)
  28.         {
  29.             sum=sum+array[j];
  30.             if(sum>largest)
  31.             {
  32.                 m=i;l=j;
  33.                 largest=sum;
  34.             }
  35.         }
  36.     }
  37.  
  38.     printf("\n The largest contigous subarray is");
  39.     for(int z=m;z<=l;z++)
  40.     {
  41.         printf(" %d ",array[z]);
  42.     }
  43.     printf("\n The sum of the largest contigous subarray is");
  44.     printf(" %d",largest);
  45.     return 0;
  46. }
Program Explanation

1. Take the size of the array as input from users.
2. Then, Initialize an array of size given by the user.
3. Using for loop, take array element as input from users and insert them into the array.
4. After inserting all the elements of the array, consider the very first element of array to be the largest.
5. Run a for loop, from 1 to arraySize-1, extracting array element one by one.
6. Run another loop inside this loop and sum every possible contiguous subarray.
6. If the largest element is smaller than the sum of the current contiguous subarray, then the largest element is updated to the current sum.
7. In the end, the largest element will hold the actual largest sum.

Runtime Test Cases

Here is the runtime output of the C program where the user is reading an array of 8 elements with values as -1,-5,5,3,-2,5,4 and 1 and then it displays the largest contigous subarray with its sum.

Type the length of the array
8
type the elements of the array
-1
-5
5
3
-2
5
4
1
 
The largest contiguous subarray is 5  3  -2  5  4  1
The sum of the largest contiguous subarray is 16

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn