力扣 1109. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
方案一：通过前缀和和前缀最小值的差求最大子序和。
func maxSubArray(nums []int) (ans int) {
n := len(nums)
// 定义前缀和和前缀和最小值
// 思路：前缀和减去前缀最小值即最大子序和
preSum, preMin := make([]int, n + 1), make([]int, n + 1)
// 计算前缀和
for i := 1; i <= n; i++ {
preSum[i] = preSum[i - 1] + nums[i - 1]
}
// 计算前缀和最小值
for i := 1; i <= n; i++ {
preMin[i] = min(preMin[i - 1], preSum[i])
}
// 定义一个题目范围的最小值，因为是通过 max 求值，定义默认值的话，可能会出现结果小于 0
ans = -100000
for i := 1; i <= n; i++ {
// 最大子序和等于前缀和减去上一个元素的前缀和最小值
ans = max(ans, preSum[i] - preMin[i - 1])
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
- 时间复杂度：O(n)，因为需要进行多次复杂度为 O(n) 的遍历，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了两个长度为 n + 1 的辅助数组保存前缀和结果，所以空间复杂度为 O(n)。