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
Top comments (0)