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