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 = 0
4. 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?