Kadane's algorithm
Finding the sum of contiguous sub-array within an array of numbers is called by Kadane's algorithm.The intuitive algorithm is check the all the sum of sub-array and choose the largest sum.
Here's the code which can get the maximum sum of sub-array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <stdio.h> int getMaxSumSubArray(int *arr, int length) { int sum = 0; int maxSum = 0; int start = 0; int end = 0; // i is the subarry start point for (int i = 0; i < length; i++) { sum = 0; // Reset sum when array start is changed. for (int j = i; j < length; j++) { sum += arr[j]; if (sum > maxSum) { maxSum = sum; start = i + 1; // Start from 1 end = j + 1; // Start from 1 } } } printf ("The maximum sum of sub-array is %d\n", maxSum); printf ("The maximum sum of sub-array starts from %d to %d\n", start, end); return maxSum; } int main() { int inputArray[] = {-1, -5, 3, -2, 4, 5, 2, 7, 4, 3, -9, 5, 3, 6, -9, -3}; // Get a length of the inputArray int arrayLength = (int) (sizeof (inputArray) / sizeof (int)); getMaxSumSubArray(inputArray, arrayLength); } |
The result of the this code is shown below.
The maximum sum of sub-array is 31 The maximum sum of sub-array start from 3 to 14
This intuitive algorithm is not the best and we can change it more efficiently.
The start sub-array index can be determined without checking all the sum of the sub-arrays and the idea is that the sub-array sum is start from the first index and re-start the sub-array summation when the sum is negative value. Because if the sum is negative in the middle of summation, the next sum is less than the next value so we have to start from the next value to get a maximum sum of the sub-array.
Here's the final code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <stdio.h> int getMaxSumSubArray(int *arr, int length) { int sum = 0; int maxSum = 0; int start = 0; int end = 0; // i is the subarry start point for (int i = 0; i < length; i++) { sum += arr[i]; if (sum > maxSum) { maxSum = sum; end = i + 1; // Start from 1 } if (sum < 0) { sum = 0; start = i + 1; // Strat from the next item start += 1; // Start from 1 } } printf ("The maximum sum of sub-array is %d\n", maxSum); printf ("The maximum sum of sub-array starts from %d to %d\n", start, end); return maxSum; } int main() { int inputArray[] = {-1, -5, 3, -2, 4, 5, 2, 7, 4, 3, -9, 5, 3, 6, -9, -3}; // Get a length of the inputArray int arrayLength = (int) (sizeof (inputArray) / sizeof (int)); getMaxSumSubArray(inputArray, arrayLength); } |
The result of the this code is shown below. That's the same as the result of the intuitive algorithm.
The maximum sum of sub-array is 31 The maximum sum of sub-array start from 3 to 14
#Kadane, #algorithm, #MaximumSubarray
