Python3 O(n) using Kadane's algorithm


  • 0
    I
    def maxSubArray(self, nums):
            maxEnd = nums[0]
            maxSub = nums[0]
            leftInd = rightInd = 0
            lang = len(nums)
            i = 1
            while (i<lang):
                if maxEnd < 0:
                    leftInd = i
                    maxEnd = nums[i]
                else:
                    maxEnd = maxEnd + nums[i]
                if maxEnd > maxSub:
                    rightInd = i
                    maxSub = maxEnd
                i = i+1
            return maxSub
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.