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 intvar current intvar negZeroNum intvar negZeroMax intfor 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
}