j
jaryue
V1
2023/05/11阅读:10主题:默认主题
leetcode 53. 最大子数组和
leetcode 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 <= 105 -104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
解题思路
法1
方法1:动态规划\
-
申请一个变量用于记录子数组的和值,如果和为负数,则需要重新记录和值
比如[1,-2,3,-1,2]那么开始数值为1,遍历到第二个数时和为-1,那么需要重新记录,值为n2,直到为正值时才继续连续记录,最后后面都不会为负数,最后最大的就是[3,-1,2]=4
-
再申请一个变量来记录最大的值,当当前数组的和大于最大值时,将赋值给最大值.
-
时间复杂度(O(n)) -
空间复杂度(O(1))
执行结果
法1
动态规划。
我们遍历整个数组,维护两个变量:currentSum表示当前子数组的和,maxSum表示到目前为止的最大和。我们从左到右逐个元素遍历数组,对于每个元素,如果currentSum为负数,则重新开始计算子数组和,否则将当前元素加到currentSum中。然后我们更新maxSum为当前maxSum和currentSum中的较大值。最后返回maxSum作为结果。
func maxSubArray(nums []int) int {
maxSum := nums[0]
currentSum := 0
for _, num := range nums {
// 如果当前和为负数,则重新开始计算子数组和
if currentSum < 0 {
currentSum = num
} else {
currentSum += num
}
// 更新最大和
if maxSum<currentSum{maxSum=currentSum}
}
return maxSum
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 100 ms , 在所有 Go 提交中击败了 38.52% 的用户 内存消耗: 8.6 MB , 在所有 Go 提交中击败了 73.29% 的用户 通过测试用例: 210 / 210 炫耀一下:
作者介绍
j
jaryue
V1