Maximum Subarray Sum

maxSubarraySum.py

class Solution:
    
    # Dynamic Programming: Time: O(n) Space O(n)
    def maxSubArrayDP(self, nums: List[int]) -> int:
        
        if not nums:
            return 0
        
        maxSum = nums[0]
        DP = [0]*len(nums) # DP will hold the max sum so far
        DP[0] = maxSum
        
        for i in range(1, len(nums), 1):
            
            DP[i] = max(nums[i], DP[i-1]+nums[i])
            maxSum = max(DP[i], maxSum)
            
        return maxSum
        
        
    # Optimized: Time: O(n) Space: O(1)
    def maxSubArray(self, nums: List[int]) -> int:
        
        if not nums:
            return 0
        
        maxSum = nums[0]
        currSum = maxSum
        
        for i in range(1, len(nums), 1):
            currSum = max(nums[i], currSum + nums[i])
            maxSum = max(currSum, maxSum)
            
        return maxSum
        

53. Maximum Subarray
Walk Through - YouTube
Walk Through - Vimeo