Kadane+count negatives. Readable

programming
Tags: #<Tag:0x00007f182863da70>

#1

A very basic kadane impllementation with counting the negatives in the same loop. Although , I dont wanna check the if condition on evey loop for negative number. Do let me know if you have a better approach

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maxSubArray(self, A):
        negatives = 0
        cur_sum = 0
        max_sum = 0
        if len(A)==1:
            return A[0]
        for i in range(len(A)):
            if A[i]<0:
                negatives+=1
            cur_sum+=A[i]
            max_sum = max(cur_sum,max_sum)
            if cur_sum < 0:
                cur_sum = 0
        return max_sum if negatives!=len(A) else max(A)

#2

I tried with all function. I think effectively both has the same complexity of O(N).
‘’’
def maxSubArray(self, A):
currSum = 0
maxSum = 0

    if len(A) == 1:
        return A[0]
    if all(i <0 for i in A):
        return max(A)
    
    for i in range(1, len(A)-1):
        currSum = max(A[i], A[i]+currSum)
        maxSum = max(maxSum, currSum)
    return maxSum

‘’’