Kadane's algorithm fails to satify the condition when first number is negative

My algorithm is as shown below:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

On the basis of that, the code that I have written is as shown below:

def maxSubArraySum(a,size):

    max_so_far = 0
    max_ending_here = 0

    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if max_ending_here < 0:
            max_ending_here = 0

        # Do not compare for all elements. Compare only   
        # when  max_ending_here > 0
        elif (max_so_far < max_ending_here):
            max_so_far = max_ending_here

    return max_so_far

# Driver function to check the above function 
a = [-1,-2,-3,-4]
print ("Maximum contiguous sum is", maxSubArraySum(a,len(a))).

This code somehow gives me output 0 when the array is [-1,-2,-3,-4]. Is there anything which I should rectify in my current code?

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this).

As such, a list with all negative numbers will trip the algorithm. If you think about it though, maximum sum of all negative integer list is nothing but max(list_of_negative_integers).

However, if you want to create a generic solution,

• add another variable max_in_array and a flag.
• set flag on
• loop through items
  • Keep the max_in_array up-to-date while looping.
  • set the flag off, if you find a positive number.
  • do the existing logic to update two variables you already have
• if the flag is off, return max_so_far otherwise max_in_array

Here is an implementation for reference:

def max_sub_array_sum(arr):
    max_so_far = max_ending_here = 0
    max_in_arr = arr[0]
    flag = True

    for item in arr:
        if flag:
            max_in_arr = max(max_in_arr, item)

        max_ending_here = max(0, max_ending_here + item)
        max_so_far = max(max_so_far, max_ending_here)

        if item > 0:
            flag = False

    return max_in_arr if flag else max_so_far

Another approach without extra vars:

def max_sub_array_sum(arr):
    max_so_far = curr_max = arr[0]

    for item in arr[1:]:
        curr_max = max(item, curr_max + item)
        max_so_far = max(max_so_far, curr_max)

    return max_so_far