题目
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)
。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1]
的和最大,为 6。
提示:
- 1 <= arr.length <= 10^5
-
方案
func maxSubArray(nums []int) int {
if len(nums) == 0 {
return 0
}
// 动态规划数组为 dp,dp[i] 表示以 nums[i] 结尾的连续子数组最大和
dp := []int{nums[0]}
max := nums[0]
for i := 1; i < len(nums); i++ {
if dp[i-1] > 0 {
dp = append(dp, dp[i-1]+nums[i])
} else {
dp = append(dp, nums[i])
}
if dp[i] > max {
max = dp[i]
}
}
return max
}
状态定义:动态规划数组为
dp
,dp[i]
表示以nums[i]
结尾的连续子数组最大和- 状态转移方程:
- 当
dp[i - 1] > 0
时,则dp[i] = dp[i-1] + nums[i]
,因为此时dp[i - 1]
产生正向增益,所以要加上去 - 当
dp[i - 1] ≤ 0
时,则dp[i] = nums[i]
,因为此时dp[i - 1]
产生负向增益,所以不需要添加参考链接
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsiyed/
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsus9h/
- 当