53. Maximum Sum Subarray

Easy

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

😇 Solution

O(n)

#Dynamic Programming - memoization

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        dp = [0 for i in range(len(nums))]
        res = dp[0] = nums[0]
        
        for i in range(1,len(nums)):
            dp[i] = max( (dp[i-1]+nums[i]) , nums[i] )
            res = max(res , dp[i])
        return res

O(n2)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        max_sum = nums[0]
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                temp = sum(nums[i:j+1])
                if temp > max_sum:
                    max_sum = temp
        return max_sum