53.最大子序和

leetcode

思路：动态规划，前缀和。

func maxSubArray(nums []int) int {

	ans := nums[0]
	
	for i := 1; i < len(nums); i++ {
		// 当前缀和为正数则累加，否则抛弃
		if nums[i-1] + nums[i] > nums[i] {
			nums[i] = nums[i-1] + nums[i]
		}
	
		if nums[i] > ans {
			ans = nums[i]
		}
	}
	
	return ans
}