53.M 最大子数组和

Problem: 53. 最大子数组和

思路

动态规划。

令f(i)为以i结尾的子数组的最大和。然后有：

状态转移方程：f(i) = max(f(i-1) + nums[i], nums[i])

由于f(i)仅跟f(i-1)相关，所以实际不需要创建一个数组，只需要用pre代表上一次计算的结果即可。

该解法的时间复杂度为O(N)，空间复杂度为O(1)

Code

func maxSubArray(nums []int) int {
	pre, ans := 0, nums[0]
	for _, num := range nums {
		pre = max(pre+num, num)
		ans = max(ans, pre)
	}

	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}