C Exercises: Find the maximum circular subarray sum of a given array

Last update on March 18 2025 13:21:18 (UTC/GMT +8 hours)

51. Maximum Circular Subarray Sum

Write a program in C to find the maximum circular subarray sum of a given array.

Expected Output :
The given array is : 10 8 -20 5 -3 -5 10 -13 11
The maximum circular sum in the above array is: 29

To solve the problem of finding the maximum circular subarray sum in a given array, the program needs to handle two scenarios: the maximum sum subarray that does not wrap around and the maximum sum subarray that does wrap around the array. The solution involves using Kadane's algorithm to find the maximum subarray sum for both scenarios and then determining the overall maximum. This approach ensures efficient computation of the desired result.

Visual Presentation:

C Exercises: find the maximum circular subarray sum of a given array

Sample Solution:

C Code:

#include <stdio.h>

// Function to find the maximum sum using Kadane's algorithm
int kadane(int arr1[], int n);

// Function to find the maximum circular sum of a subarray
int SumOfMxCircur(int arr1[], int n)
{
    // Find maximum sum using Kadane's algorithm
    int maxKadaneSum = kadane(arr1, n);

    int maxWrap = 0, i;
    // Calculate the sum of the whole array and invert its elements
    for (i = 0; i < n; i++)
    {
        maxWrap += arr1[i];
        arr1[i] = -arr1[i];
    }

    // Find maximum circular sum by adding the total sum and Kadane's algorithm for inverted array
    maxWrap = maxWrap + kadane(arr1, n);

    // Return the maximum of maxWrap and maxKadaneSum
    return (maxWrap > maxKadaneSum) ? maxWrap : maxKadaneSum;
}

// Function to find the maximum sum of subarray using Kadane's algorithm
int kadane(int arr1[], int n)
{
    int maxUpto = 0, maxAtPos = 0;
    int i;
    for (i = 0; i < n; i++)
    {
        maxAtPos = maxAtPos + arr1[i];
        if (maxAtPos < 0)
            maxAtPos = 0;
        if (maxUpto < maxAtPos)
            maxUpto = maxAtPos;
    }
    return maxUpto;
}

// Main function
int main()
{
    int arr1[] = {10, 8, -20, 5, -3, -5, 10, -13, 11};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int i;

    // Print the original array
    printf("The given array is:  ");
    for (i = 0; i < n; i++)
    {
        printf("%d  ", arr1[i]);
    }
    printf("\n");

    // Find and print the maximum circular sum in the array
    printf("The maximum circular sum in the above array is:  %d\n", SumOfMxCircur(arr1, n));

    return 0;
}

Output:

The given array is :  10  8  -20  5  -3  -5  10  -13  11  
The maximum circular sum in the above array is:  29

Flowchart:/p>

For more Practice: Solve these Related Problems:

Write a C program to compute the maximum circular subarray sum using Kadane’s algorithm adapted for circular arrays.
Write a C program to find the maximum circular subarray sum and then output the subarray indices.
Write a C program to calculate the maximum circular subarray sum using two passes: one for non-circular and one for circular cases.
Write a C program to determine the maximum circular subarray sum and compare it with the standard maximum subarray sum.

C Programming Code Editor:

Previous: Write a program in C to print a matrix in spiral form.
Next: Write a program in C to count the number of triangles can be fromed from a given array.