Kadane's algorithm can be USED to find the maximum subarray sum for a given array.  From left to right, Kadane's algorithm searches the provided array. It then computes the subarray with the largest sum ENDING at position j in the jth step, and this sum is stored in the variable "currentSum". Furthermore, it computes the subarray with the biggest sum anywhere in the subarray starting from the first position to the jth position, that is, in A[1...j], and stores it in the variable "bestSum". This is done by taking the maximum value of the variable "currentSum" till now and then storing it in the variable "bestSum".  In the end, the value of "bestSum" is returned as the final answer to our problem.

Formally, Kadane's algorithm can be stated as follows:

• Step 1: Initialize the following variables:
  • bestSum = INT_MIN
  • currentSum = 0 // for empty subarray, it is initialized as value 0
• Step 2: Loop for each element of the array A
  • (a) currentSum  = currentSum  + A[i]
  • (b) if(bestSum < currentSum)
               bestSum = currentSum 
  • (c) if(currentSum  < 0)
               currentSum = 0
• Step 3: return bestSum