C Program to Find the Largest Sum of Contiguous Subarray of an Array

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:

-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.

advertisement
advertisement

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

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.

  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.

advertisement
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.

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

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.