In this blog post, we learn how to write a C program to find a contiguous subarray which has the largest sum and returns its sum? So here we will write a C program to find the sum of contiguous subarray within a one-dimensional integer array which has the largest sum. We will also see how to display the largest sum of contiguous subarray within a one-dimensional integer array ‘arr’ of size N using C programming.
Example,
Input: int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
Output: 6
Explanation:{4,-1,2,1} has the largest sum = 6.Largest contiguous subarray sum solution in C:
We can solve this problem easily using Kadane’s algorithm in O(n) time complexity. Kadane’s algorithm scans the given array arr[1..N] from left to right and computes the maximum sum ending at every index (max_ending_here).
1. Create two intermediate variables max_ending_here and max_so_far.
2. Initialized these two intermediate variables using the 0.
3. Traverse the array from 0 to N-1 and calculate the max_ending_here and max_so_far.
(a) max_ending_here = max_ending_here + arr[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 04. Now we will keep max_so_far which indicates the maximum sum found so far.
If you want to learn more about the C language, you can check this course, Free Trial Available.
#include <stdio.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
// Function to return max subarray sum
int maxSubArraySum(int arr[], int n)
{
int i =0;
// stores maximum sum subarray found so far
int max_so_far = 0;
// stores the maximum sum of subarray ending at the current position
int max_ending_here = 0;
// traverse the given array
for ( i = 0; i < n; i++)
{
// update the maximum sum of subarray "ending" at index `i`
max_ending_here = max_ending_here + arr[i];
// if the maximum sum is negative, set it to 0
if (max_ending_here < 0)
{
max_ending_here = 0; // empty subarray
}
// update result if the current subarray sum
//is greater than last stored sum
if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
}
}
return max_so_far;
}
int main()
{
int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
//get array size
int arr_size = ARRAY_SIZE(arr);
const int maxSum = maxSubArraySum(arr, arr_size);
printf("%d ", maxSum);
return 0;
}
If you want, you can also print the sub-array start and end indexes with subarray elements. In the below program I am tracking the start and last index of the array which has a max sum.
#include <stdio.h>
#include<limits.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
int maxSubArraySum(int arr[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0;
int start =0, end = 0, s=0;
int i = 0;
for ( i=0; i< size; i++ )
{
max_ending_here += arr[i];
if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
start = s;
end = i;
}
if (max_ending_here < 0)
{
max_ending_here = 0;
s = i + 1;
}
}
printf("Sub array start index = %d\n", start);
printf("Sub array last index = %d\n", end);
//printing sub array which contains max sum
printf("Sub array is = ");
for (i = start; i <= end; i++)
{
printf("%d ", arr[i]);
}
return max_so_far;
}
int main()
{
int arr[] = { -2, -1, -3, -4, -1, -2, 1, 0, 2, -1};
//get array size
int arr_size = ARRAY_SIZE(arr);
const int maxSum = maxSubArraySum(arr, arr_size);
printf("\n%d ", maxSum);
return 0;
}
Output:
Sub array start index = 6
Sub array last index = 8
Sub array is = 1 0 2
Max sum = 3
If you don’t want to get the sub-array indexes and sub-array, then you can also use a simple code to get find the max of the subarray. So let’s see the code,
#include <stdio.h>
#include<limits.h>
//Calculate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
//Get max value
#define MAX(a,b) (a>b)?a:b
int maxSubArraySum(int a[], int n)
{
int max_so_far = a[0];
int curr_max = a[0];
int i = 0;
for (i = 1; i < n; i++)
{
curr_max = MAX(a[i], curr_max+a[i]);
max_so_far = MAX(max_so_far, curr_max);
}
return max_so_far;
}
int main()
{
int arr[] = { -2, -1, -3, -4, -1, -2, 1, 0, 2, -1};
//get array size
int arr_size = ARRAY_SIZE(arr);
const int maxSum = maxSubArraySum(arr, arr_size);
printf("\nMax sum = %d\n", maxSum);
return 0;
}
Output:
Max sum = 3
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to find the Median of two sorted arrays of different sizes.
- C Program to find first and last position of element in sorted array
- Write C program to find the missing number in a given integer array of 1 to n
- C program to find the most popular element in an array
- Find the largest and smallest element in an array using C programming.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- 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.
- C program to find odd occurring elements in an array of limited range
- 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?
One comment