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.