Maximum Subarray Problem ( Kadane’s Algorithm) Dynamic Programming

Maximum SubArray Sum is the problem of finding the sum of contiguous subarray elements with in an array of numbers form arr[1...n]

You might ask what is a subarray?

SubArray is basically array within an array is called a sub array, as shown below 4, -1, 2 is the subarray of the given array arr[], So,  a subarray is a set of contiguous elements in a given array.

Exxample :

Given an array of n elements

For example, for the array given above, the contiguous subarray with the largest sum is [4, -1, 2], with sum 5. We would use this array as our example. Also, we would assume this array to be zero-indexed, i.e. -2 would be called as the ‘0th’ element of the array and so on. Also, A[i] would represent the value at index i.

Kadane’s Algorithm:

From the example we see that the local maximum is [4] which on adding to the next element is 3 as the elements are [4, -1] , now when we move forward in the  subarray we find the element [2] which sums up to give the result as 5. Therefore the maximum sum of the sub array is 5,

So Kadane’s Algorithm starts doing the sum with the max element found in the array because if the elements are in the negative order there is no need to carry the element forward, as we will see in the code below. Whenever the local_max element is found in the array it updates the max variable to keep track of the maximum sum subarray.

class maxSum{
public int maxSubArray(int[] arr) {
int sum = 0;
int max = arr[0];
for(int i = 0; i < arr.length; i++){
sum += arr[i];
if(sum > max) max = sum;
if(sum < 0) sum = 0;
}
return max;
}
}

Code Explanation:

This is a very much self-explanatory implementation (in Java) of a function which takes an array as an argument and returns the sum of the maximum subarray.

Side Note:  Instead of using an array to store maximum, we are simply storing the latest maximum in an int type variable ‘max’ because that’s what we need to calculate next maximum. Also, as we are using a variable ‘max’ to keep track of the maximum value of maximum, which in the end comes out to be the required output.

Conclusion:

Because of the way this algorithm uses optimal substructures, this algorithm can be viewed as a simple example of dynamic programming. Kadane’s algorithm is able to find the maximum sum of a contiguous subarray in an array with a runtime of O(n).