一、问题描述

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

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

提示：

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

---

二、方案一：动态规划

1、思路

动态规划的核心思想是：将大问题分解为小问题，通过解决小问题来解决大问题。对于本题，我们可以定义一个一维数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最大子数组和。那么，对于每个 nums[i]，我们有两个选择：

1. 将 nums[i] 加入到 dp[i-1] 对应的子数组中，形成新的子数组。
2. 单独将 nums[i] 作为子数组。 我们需要在这两个选择中选择一个使得 dp[i] 最大的方案。

2、代码实现

func maxSubArray(nums []int) int {
    n := len(nums)
    // dp[i] 表示以 nums[i] 结尾的最大子数组和
    dp := make([]int, n)
    dp[0] = nums[0]
    maxSum := dp[0]
    for i := 1; i < n; i++ {
        // 选择 nums[i] 加入到 dp[i-1] 对应的子数组中，或者单独作为子数组
        dp[i] = max(nums[i], nums[i]+dp[i-1])
        maxSum = max(maxSum, dp[i])
    }
    return maxSum
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组。
• 空间复杂度：O(n)，我们需要一个长度为 n 的数组 dp 来存储中间结果。

---

三、方案二：贪心算法

1、思路

贪心算法的核心思想是：每一步都做出在当前看来最好的选择。对于本题，我们可以这样考虑：如果当前累加的和小于等于 0，那么这个累加的和对于后续的累加是没有帮助的，我们可以将其抛弃，从下一个元素开始重新累加。这样，我们只需要遍历一次数组，就可以找到最大子数组和。

2、代码实现

func maxSubArray(nums []int) int {
    maxSum := nums[0]
    currentSum := 0
    for _, num := range nums {
        // 如果当前累加和小于等于 0，则抛弃，从下一个元素开始重新累加
        if currentSum <= 0 {
            currentSum = num
        } else {
            currentSum += num
        }
        maxSum = max(maxSum, currentSum)
    }
    return maxSum
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只需要常数级别的额外空间来存储变量。

---

四、总结

方案	时间复杂度	空间复杂度	说明
动态规划	O(n)	O(n)	需要一个数组来存储中间结果
贪心算法	O(n)	O(1)	只需要常数级别的额外空间
从时间和空间复杂度来看，贪心算法是更优的选择。同时，贪心算法的实现也更加简洁。因此，推荐使用贪心算法来解决这个问题。