C program to find contiguous subarray which has the largest sum and returns its sum

January 28, 2021

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.

Get Your Free Trial 
#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;
}
max sum subarray

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: