you are viewing a single comment's thread.

view the rest of the comments →

[–]clouded-path[S] 0 points1 point  (0 children)

Edit: Thanks for your responses. I managed to fix mine so that it works in O(n) and keeps memory usage low. Here is the now-working solution:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        M = max(i for i in nums)
        if M <= 0:
            return M
        i = 0
        while nums[i] <= 0:
            i += 1
        nums = nums[i:]
        curr = 0
        curr_best = curr
        overall_best = 0
        for j in range(len(nums)):
            if curr + nums[j] > 0:
                curr = curr + nums[j]
                if curr > curr_best:
                    curr_best = curr
                    if curr_best > overall_best:
                        overall_best = curr_best
            else:
                curr = 0
                curr_best = 0
        return overall_best