Python DP Solution with explanation. O(N) space and O(1) space.


  • 0
    L

    At each step there are two possibilities. Either the previous(i-1)th number was included or it was not included. We chose the one which maximizes the total sum till ith number.
    So,
    dp[i] = max(dp[i-1]+nums[i],0+nums[i])
    Now, going back to the problem definition we need to find max subarray which will be include nums[i:j] . In order to find this , we need to look at dp[j] . As per the definition of the problem this has to be maximum sum. so max(dp) will give us the result.

    def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
                
            dp = [0]*len(nums)
            dp[0] = nums[0]
            
            for i in range(1,len(nums)):
                dp[i] = max(dp[i-1]+nums[i],nums[i])
            
            return max(dp)
    

    We can further optimize the space complexity by noticing that we only need dp[i-1] to calculate dp[i] and one more variable to keep track of maximum so far.

    def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
                
            cur = nums[0]
            max_arr = nums[0]
            for i in range(1,len(nums)):
                cur = max(cur+nums[i],nums[i])
                max_arr = max(cur,max_arr)
                
            return max_arr
    

Log in to reply
 

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