53. 最大字数组和

题目描述：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

---

解题分析及思路：

这个问题可以使用动态规划的思想来解决。我们定义一个状态 dp[i] 表示以 nums[i] 结尾的最大子数组和。通过迭代数组 nums，我们可以逐步计算每个位置的最大子数组和，并更新全局最大子数组和。

具体而言，对于每个位置 i，我们比较两个选择：

• 将 nums[i] 加入当前子数组，形成新的子数组。
• 以 nums[i] 为起点开始新的子数组。

我们选择这两者中的较大值作为以 nums[i] 结尾的最大子数组和 dp[i]。然后，我们更新全局最大子数组和。

那么对应动态规划解法：

1. 定义状态： 定义状态 dp[i] 表示以 nums[i] 结尾的最大子数组和。

2. 找到状态转移方程： 对于位置 i，我们有两个选择：

   • 将 nums[i] 加入当前子数组，形成新的子数组。这时，dp[i] = nums[i]。
   • 以 nums[i] 为起点开始新的子数组。这时，dp[i] = nums[i] + dp[i-1]。

   综合两者，我们选择 dp[i] 的较大值。 状态转移方程为：dp[i] = max(nums[i], nums[i] + dp[i-1])。

3. 初始化： 将第一个元素作为初始状态，即 dp[0] = nums[0]。

4. 递推求解： 通过迭代数组，计算每个位置的最大子数组和，并更新全局最大子数组和。

5. 计算最终结果： 全局最大子数组和即为最终结果。

优化：

我们可以对方法一进行空间复杂度优化，使空间复杂度从 O(N) 降低至 O(1)。

由于 dp[i] 只与 dp[i-1] 和 nums[i] 有关系，因此我们可以将原数组 nums 用作 dp 列表，即直接在 nums 上修改即可。

优化后对应动态规划解法：

1. 定义状态： 定义状态 nums[i] 表示以 nums[i] 结尾的最大子数组和。

2. 找到状态转移方程： 对于位置 i，我们有两个选择：

   • 将 nums[i] 加入当前子数组，形成新的子数组。这时，nums[i] = nums[i]。
   • 以 nums[i] 为起点开始新的子数组。这时，nums[i] = nums[i] + nums[i-1]。

   综合两者，我们选择 nums[i] 的较大值。 状态转移方程为：nums[i] = max(nums[i], nums[i] + nums[i-1])。

3. 初始化： 将第一个元素作为初始状态，即 nums[0] = nums[0]。

4. 递推求解： 通过迭代数组，计算每个位置的最大子数组和，并更新全局最大子数组和。

5. 计算最终结果： 全局最大子数组和即为最终结果。

func maxSubArray(nums []int) int {
	maxFunc := func(i, j int) int {
		if i > j {
			return i
		}
		return j
	}
	maxNumber := nums[0]
	for index := 1; index < len(nums); index++ {
		nums[index] = maxFunc(nums[index], nums[index]+nums[index-1])
		if nums[index] > maxNumber {
			maxNumber = nums[index]
		}
	}
	return maxNumber
}

复杂度：

• 时间复杂度：O(N)，其中 N 为数组 nums 的长度。只需遍历一次数组。
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:87 ms,击败了42.34% 的Go用户
• 内存消耗:8.3 MB,击败了45.34% 的Go用户