Bug Report for maximum-subarray

[gbhardwaj00]

Bug Report for https://neetcode.io/problems/maximum-subarray

Please describe the bug below and include any steps to reproduce the bug or screenshots if possible.

There is no bug, but I wanted to provide easier solutions for the Dynamic Programming cases:

Top-Down:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        memo = {}
        best = nums[0]

        def dfs(i):
            if i in memo:
                return memo[i]

            if i == 0:
                memo[0] = nums[0]
                return memo[0]

            memo[i] = max(nums[i], dfs(i - 1) + nums[i])

            return memo[i]

        for i in range(n):
            best = max(best, dfs(i))

        return best

Bottom-up:

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

        return maxSum