代码挑战: 最大子数组 | Go

举报
Jet Ding 发表于 2021/07/23 16:10:03 2021/07/23
【摘要】 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.Example:Input: [-2,1,-3,4,-1,2,1,-5,4],Output: 6Explanation: ...

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

方案:


func maxSubArray(nums []intint {
    result := nums[0]
    temp := nums[0]
    for i := 1; i < len(nums); i++ {
        temp = int(math.Max(float64(nums[i]), float64(nums[i]+temp)))
        result = int(math.Max(float64(temp), float64(result)))
    }
    return result
}

测试案例:

func Test_maxSubArray(t *testing.T) {
    type args struct {
        nums []int
    }
    tests := []struct {
        name string
        args args
        want int
    }{
        {"test1", args{nums: []int{-2, -34, -1, -215, -3}}, 7},
        {"test2", args{nums: []int{-21, -34, -121, -54}}, 6},
        {"test3", args{nums: []int{-2}}, -2},
    }
    for _tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            if got := maxSubArray(tt.args.nums); got != tt.want {
                t.Errorf("maxSubArray() = %v, want %v", got, tt.want)
            }
        })
    }
}

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。