題目

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

貪心算法

貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。
如果現(xiàn)在的和成了負(fù)數(shù)，那么就從下一個(gè)大于0的數(shù)字開(kāi)始

func maxSubArray(nums []int) int {if len(nums) == 1{return nums[0]}var currSum, maxSum = 0, nums[0]for _, v := range nums {if currSum > 0 {currSum += v} else {currSum = v}if maxSum < currSum {maxSum = currSum}}return maxSum }

動(dòng)態(tài)規(guī)劃

在整個(gè)數(shù)組或在固定大小的滑動(dòng)窗口中找到總和或最大值或最小值的問(wèn)題可以通過(guò)動(dòng)態(tài)規(guī)劃（DP）在線性時(shí)間內(nèi)解決。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解
找到當(dāng)前區(qū)間的最優(yōu)解，而貪心算法是

func maxSubArray(nums []int) int {max_sum := nums[0]for i := 1; i < len(nums); i++ {if nums[i - 1] > 0 {nums[i] += nums[i - 1]} if nums[i] > max_sum {max_sum = nums[i]} }return max_sum }

參考

動(dòng)態(tài)規(guī)劃和貪心算法

總結(jié)

以上是生活随笔為你收集整理的53. 最大子序和 golang （动态规划与贪心算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。