LeetCode 53. 最大子数组和

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 53. 最大子数组和

思路分析

我们可以使用动态规划来解决这个问题。设 cur 为以 nums[i] 结尾的最大子数组和。我们可以通过以下步骤来更新 cur：

如果 cur + nums[i] 大于 nums[i]，则更新 cur 为 cur + nums[i]，表示我们选择继续加上当前元素。

否则，更新 cur 为 nums[i]，表示我们从当前元素重新开始一个新的子数组。

同时维护一个 res 变量，记录到目前为止的最大和。

这样，我们只需要遍历一次数组即可得到结果。

参考代码

func maxSubArray(nums []int) int {
	// 初始化 cur 和 res
	cur := nums[0]
	res := nums[0]

	// 遍历数组
	for i := 1; i < len(nums); i++ {
		// 更新 cur
		if cur+nums[i] > nums[i] {
			cur += nums[i]
		} else {
			cur = nums[i]
		}
		// 更新 res
		if cur > res {
			res = cur
		}
	}
	return res
}

func maxSubArray(nums []int) int {
	cur := nums[0] // 当前子数组和
	res := nums[0] // 最大子数组和

	for i := 1; i < len(nums); i++ {
		// 更新当前子数组和
		if cur < 0 {
			cur = nums[i] // 重新开始
		} else {
			cur += nums[i] // 加入当前元素
		}
		// 更新最大子数组和
		if cur > res {
			res = cur
		}
	}
	return res
}

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需遍历一次数组。

空间复杂度：O(1)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/31655177