# 53.M 最大子数组和

> Problem: [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/description/)

## 思路

动态规划。

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

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

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

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

## Code

```go
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
}
```