Largest Contiguous Subarray Sum in O(n) : Kadane's Algorithm

Another important algorithm that is commonly used for finding the largest contiguous subarray sum in linear time is Kadane's algorithm. The pseudocode for the algorithmm is given below:

msf = 0
meh = 0
for each element in the array
    meh = meh + A[i]
    if meh < 0:
        meh = 0
    if msf < meh:
        msf = meh
return msf