Maximum Subarray
Given an array, find the subarray with the maximum sum. Tags: Dynamic Programming
Try It!
Discussion
Video
Solution
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = nums[0]
cur_total = 0
for n in nums:
cur_total += n
ans = max(ans, cur_total)
if cur_total < 0:
cur_total = 0
return ans