Largest sum of sub-arrays using Kadane's algorithm

Sub-arrays

A sub-array is a contiguous part of an array that inherently maintains the order of elements. An array that is inside another array. For example, the sub-arrays of an array {1, 2, 3} are {1}, {2}, {3}, {1, 2}, {2, 3} and {1, 2, 3}.

Kadane's algorithm

Kadane's algorithm is used to find the “Maximum sub-array sum” in any given array of integers. Let's consider an array arr with n values in it, then Kadane's algorithm can be applied as shown in the steps below,

• Initialize the result and max-so-far variables (res and maxEnd) by assigning first element of the array i.e., arr[0]
• Iterate through the elements of the array starting from index 1
• Override the value of maxEnd by the maximum value between maxEnd+arr[i] and arr[i]
• Override the value of res by the maximum value between maxEnd and res
• Return the result variable which will be the maximum sum of subarrays

Let arr = {-3, 8, -2, 4, -5, 6}, n = 6

Code

#include <stdio.h>

int max(int a, int b) {
    if(a>b)
        return a;
    return b;
}

// T(n) = Θ(n)
// Aux space = Θ(1)

int maxSubSum(int arr[], int n)
{
    int res = arr[0], maxEnd = arr[0];

    for(int i=1; i<n; i++)
    {
        maxEnd = max(maxEnd+arr[i], arr[i]);
        res = max(maxEnd, res);
    }

    return res;
}

int main() {
    int arr[] = {-3, 8, -2, 4, -5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int res = maxSubSum(arr, n);
    printf("%d", res);

    return 0;
}

Output

11

Thanks for reading!

If you have any questions about the post feel free to leave a comment below.

Follow me on twitter: @soorya_54