leetcode 53. 最大子数组和

leetcode 53. 最大子数组和

题目描述

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. 申请一个变量用于记录子数组的和值,如果和为负数,则需要重新记录和值

比如[1,-2,3,-1,2]那么开始数值为1,遍历到第二个数时和为-1,那么需要重新记录,值为n2,直到为正值时才继续连续记录,最后后面都不会为负数,最后最大的就是[3,-1,2]=4

2. 再申请一个变量来记录最大的值,当当前数组的和大于最大值时,将赋值给最大值.

• 时间复杂度(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 炫耀一下: