Kadane's Algorithm: Maximum Contiguous Subarray sum.

Kadane's Algorithm

Kadane's Algorithm is used to find the maximum sum of a contiguous subarray from an array. Kadane's Algorithm is an efficient approach to find the maximum contiguous subarray sum. Kadane's algorithm can handle negative numbers as well. To make Kadane's Algorithm more clear let us take an example.

In the image above we have taken an array and we need to find the maximum contiguous subarray sum. So, you will be thinking why we have made a box from index 3 to 5. So, let us proceed with this. We have taken two variables here having int datatype current_sum which will keep the track of current sum, on the other hand we have maximum_sum which will keep the track of maximum sum of an contiguous subarray. This maximum_sum will give us the required result.

Algorithm:

• Initialize current_sum = arr[0] and maximum_sum = arr[0].
• Start loop i from 1 to n (n is array length).
• if current_sum >=0 {
  current_sum + = arr[i];
  }
  else{
  current_sum = arr[i];
  }
• if (current_sum > maximum_sum)
  update maximum_sum = current_sum;
• after loop ends return maximum_sum.

Explanation:

Firstly, current_sum = arr[0]; and maximum_sum = arr[0] also
//current_sum = 9; maximum_sum = 9;

Now loop starts from 1 to n (where n is length of array).

when i=1 , current_sum >= 0 so current_sum+=arr[i] //current sum becomes 0 becuase if condition is executed
current_sum is not greater than maximum_sum so no updation of maximum_sum.

when i=2 , current_sum >=0 so current_sum+=arr[i] // current sum becomes 0 because if condition is executed
current_sum is not greater than maximum_sum so no updation of maximum_sum.

when i=3 , current_sum >=0 so current_sum+=arr[i] // current sum becomes 2 because if condition is executed
current_sum is not greater than maximum_sum so no updation of current_sum.

when i=4 , current_sum >=0 so current_sum+=arr[i] // current sum becomes 6 because if condition is executed
current_sum is not greater than maximum_sum so no updation of maximum_sum. maximum_sum is 9.

when i=5 , current_sum >=0 so current_sum+=arr[i] // current sum becomes 11 because if condition is executed
current_sum is now greater than maximum_sum so updation of maximum_sum to current_sum i.e 11. Now, maximum_sum = 11

when i=6 , current_sum >=0 so current_sum+=arr[i] // current sum becomes 9 because if condition is executed
current_sum is not greater than maximum_sum so no updation of maximum_sum. maximum_sum is 11.

Loop ends return maximum_sum.

Code Approach:(Java)

package Arrays;

/*This algorithm is used to find the maximum sum of contiguous sub-array */
/*Time Complexity is O(n) and Space complexity is O(1)*/
public class KadaneAlgorithm {
    public static void main(String[] args) {
        int[] arr = {9, -9, 0, 2, 4, 5, -3};
        int n = arr.length;
        // result will store the value returned from maxSubArraySum()method
        int result = maxSubArraySum(arr, n);
        System.out.print("Maximum contiguous subarray sum is: "+result);
    }

    public static int maxSubArraySum(int[] arr, int n) {
        int current_sum = arr[0];
        int maximum_sum = arr[0];
        for (int i = 1; i < n; i++) {
            if (current_sum >= 0) {
                current_sum += arr[i];
            } else {
                current_sum = arr[i];
            }
            if (current_sum > maximum_sum) {
                maximum_sum = current_sum;
            }
        }
        return maximum_sum;
    }
}

Output:

Maximum contiguous subarray sum is: 11

Time Complexity: Time complexity of Kadane's Algorithm is O(n) as it traverse whole array once.

Space Complexity: O(1) No extra space required.(Constant Space)