53-MaximumSubarray

Maximum Subarray

Problem can be found in here!

Solution: Prefix Sum

def maxSubArray(nums: List[int]) -> int:
    current_sum = max_sum = 0
    for num in nums:
        current_sum = max(current_sum+num, num)
        max_sum = max(max_sum, current_sum)
    return max_sum

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: