Python DP solution with detailed explanations.


  • 0
    M

    Here's how to solve it. A[i] is an array, and MS(A, i) marks the maximum subarray that ended with index i. So we have the equation:

    MS(A, i) = max(MS(A, i-1) + A[i], A[i])        (A.length > 0)
             = 0                                   (A.length = 0) 
    
    def maxSubArray(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        r = [0] * (n + 1)
        q = float('-inf')
        for i in xrange(1, len(nums) + 1):
            r[i] = max(r[i-1] + nums[i-1], nums[i-1])
            q = max(q, r[i])        
        return q
    

Log in to reply
 

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