不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

Leetcode-53-maximum-subarray | 最大子序和

发表于 更新于 分类于
本文字数： 651 阅读时长 ≈ 1 分钟

题目链接

leetcode中文
leetcode

解题思路

暴力解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxSubArray(nums []int) int {
    //一个临时值，和一个最大值
    temp,max := 0,nums[0]
    for i:=0;i<len(nums);i++ {
        if (temp + nums[i]) > nums[i] {
            temp = temp + nums[i]
        } else {
            temp = nums[i]
        }
        if temp > max {
            max = temp
        }
    }

    return max  //返回最大值
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func maxSubArray(nums []int) int {
    //dp解法
    var dp = map[int]int{}
    dp[0] = nums[0]
    max := nums[0]
    for i := 1; i < len(nums); i++ {
        //做判断
        if (dp[i - 1] + nums[i]) > nums[i] {
            dp[i] = dp[i - 1] + nums[i]
        } else {
            dp[i] = nums[i]
        }

        if dp[i] > max {
            max = dp[i]
        }
    }
    return max
}

参考资料

------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！