题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
- 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
- 输出：6
- 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
示例 3：
- 输入：nums = [5,4,-1,7,8]
- 输出：23
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解法一：动态规划
dp[i] 定义为以 nums[i] 结尾的子数组的最大和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func max(nums ...int) int {
ans := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > ans {
ans = nums[i]
}
}
return ans
}
func maxSubArray(nums []int) int {
n := len(nums)
dp := make([]int, n)
dp[0] = nums[0]
for i := 1; i < n; i++ {
if dp[i-1] < 0 {
dp[i] = nums[i]
} else {
dp[i] = dp[i-1] + nums[i]
}
}
return max(dp...)
}
|
发现求 dp[i] 时只使用到了 dp[i-1] 故可以使用 2 个变量来取代 dp 数组，并在求 dp[i] 时更新要返回的结果。优化后的代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func maxSubArray(nums []int) int {
n := len(nums)
prev, res := nums[0], nums[0]
for i := 1; i < n; i++ {
if prev < 0 {
prev = nums[i]
} else {
prev += nums[i]
}
if prev > res {
res = prev
}
}
return res
}
|
