202401170947
tags: #dp

class Solution(object):
	def maxSubArray(self, nums):
		prefixSum = nums[0]
		res = nums[0]
		for i in range(1, len(nums)):
			if prefixSum < 0:
				prefixSum = nums[i]
			else:
				prefixSum += nums[i]
			res = max(res, prefixSum)
		return res

Reference

https://leetcode.com/problems/maximum-subarray/