算法|LeetCode Golang Hot53-最大子数组和 leetcode|算法|golang

【算法|LeetCode Golang Hot53-最大子数组和】https://leetcode-cn.com/problems/maximum-subarray/
贪心算法

package mainimport "fmt"func main() { res := maxSubArray([]int{-3, -1, -5}) fmt.Println(res) }func maxSubArray(nums []int) int { if len(nums) == 0 { return 0 }var max int var current intvar negZeroNum int var negZeroMax int for i := 0; i < len(nums); i++ { if nums[i] < 0 { negZeroNum++ if negZeroNum == 1 { negZeroMax = nums[i] } else { if nums[i] > negZeroMax { negZeroMax = nums[i] } } } current += nums[i] if current < 0 { current = 0 } if current > max { max = current } } if len(nums) == negZeroNum { return negZeroMax } return max }

动态规划

package mainimport "fmt"func main() { res := maxSubArray([]int{-3, -1, -5, 3}) fmt.Println(res) }func maxSubArray(nums []int) int { if len(nums) == 1 { return nums[0] } max := nums[0] for i := 0; i < len(nums); i++ { if i == 0 { continue } if nums[i-1] > 0 { nums[i] = nums[i] + nums[i-1] } if max < nums[i] { max = nums[i] } } return max }