LeetCode-53. 最大子序和(Goland实现)

￡神魔★判官ぃ 2022-11-29 05:44 33阅读 0赞

> 题号：[53. 最大子序和][53.]
> 
> 题目描述：
> 
>          给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

> **示例:**
> 
>     输入: [-2,1,-3,4,-1,2,1,-5,4]
>     输出: 6
>     解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

优化前：

![20200819144917955.png][]

func maxSubArray(nums []int) int {
    	if len(nums) == 0 {
    		return 0
    	}
    	var max = nums[0]
    	var sum = 0
    	for i := 0; i < len(nums); i++ {
    		sum = nums[i]
    		//首先判断 当前值是否比max大，避免有可能max为负，但是当前值也为负但是比max大的情况
    		if sum > max {
    			max = sum
    		}
    		for j := i + 1; j < len(nums); j++ {
    			sum = sum + nums[j]
    			if sum > max {
    				max = sum
    			}
    		}
    	}
    	return max
    }

优化后：

![20200819144849744.png][]

//优化  只需遍历一次
    func maxSubArray1(nums []int) int {
    	var 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
    }

--------------------

> ❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ
> 
> ❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
> 
> ❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
> 
> ❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)。

[53.]: https://leetcode-cn.com/problems/maximum-subarray/
[20200819144917955.png]: /images/20221124/8b848a036b61495bba2139660fe7a38a.png
[20200819144849744.png]: /images/20221124/c89a18be1ab64c77bacafcbc4d9da2b2.png