共计 493 个字符,预计需要花费 2 分钟才能阅读完成。
题目 :给你一个整数数组 nums,请你找出一个具备最大和的间断子数组(子数组起码蕴含一个元素),返回其最大和。
子数组 是数组中的一个间断局部。
链接 :力扣 Leetcode – 53. 最大子数组和.
示例 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
思路 :使用动静布局,遍历数组,以后一个元素大于 0,则将其加到以后元素上
Go 代码:
package main
import "fmt"
func maxSubArray(nums []int) int {max := nums[0]
for i := 1; i < len(nums); i++ {if nums[i]+nums[i-1] > nums[i] {nums[i] += nums[i-1]
}
if nums[i] > max {max = nums[i]
}
}
return max
}
func main() {a := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
fmt.Println(maxSubArray(a))
}
提交截图 :
正文完