Python3 Solution (94.47% Percentile)


  • 1
    M
    class Solution:
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
    
            """
            Dynamic programming
            """
            assert nums != [], "Empty array!"
            if len(nums) == 1:
                return nums[0]
            
            max_sum = nums[0]
            max_sum_end = nums[0]
            for num in nums[1:]:
                max_sum_end = max(max_sum_end + num, num)
                max_sum = max(max_sum, max_sum_end)
            return max_sum
    

Log in to reply
 

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