This algorithm is used to find the maximum sum of a contiguous sub array in a given array of integers. If the set of integers include only positive integers, maximum sum would be sum of all the elements of array. But when the array include negative integers too, the problem comes of how to solve it efficiently.
A naive approach would be finding sum of elements of all sub arrays.
MaxSubarraySumNaive(a) max = 0 for i = 1 to n for j = i to n temp = 0 for k = i to j temp = temp + a[i] if temp > max max = temp return max
That’s an O(n3) solution which is not at all appreciable. So let’s learn this algo which could solve this problem with an O(n) complexity.
MaxSubarraySum(a) max_sum = 0 temp = 0 for i = 1 to n temp = max( 0 , temp+a[i] ) max_sum = max( max_sum , temp ) return max_sum
This short function solves the problem in real quick time. Working of the function with an example is shown below
For increasing i, Array elements : 1 -2 8 -1 6 3 -12 4 -16 5 10 temp values : 1 0 8 7 13 16 4 8 0 5 15 max_sum values : 1 1 8 8 13 16 16 16 16 16 16