README.md

Maximum Subarray

Problem can be found in here!

Solution: Dynamic Programming

def maxSubArray(nums: List[int]) -> int:
    for i in range(1, len(nums)):
        nums[i] = max(nums[i], nums[i-1]+nums[i])

    return max(nums)

Explanation: Define the maximum value of a given subarray from index 0 to i as P(i) and the original array as nums. We can easily write down the recursion function P(i) = max(nums[i], P(i-1)+nums[i]).

Time Complexity: , Space Complexity: , where n is the length of array.